Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.


Naive Way: I first came up with DFS, which get TLE. By expanding the DFS approach, I see redundancy lies in the reuse of high index calls, like (S, 4) will be called 4 times in example "1224".
So there should be a corresponding DP approach.

 public class Solution {  
   public int numDecodings(String s) {  
     return dfs(s, 0);  
   }  
   private int dfs(String s, int index){  
     // base case  
     if(index >= s.length()) return 1;  
     // recursion  
     int count = 0;  
     if(index+1 < s.length() &&(s.charAt(index) == '1' || s.charAt(index) == '2' && s.charAt(index+1) <= '6'))  
       count += dfs(s, index+2);  
     if(s.charAt(index) != '0')  
       count += dfs(s, index+1);  
     return count;  
   }  
 }  

The logic of DP can be concluded as
opt[i,j] // the # of ways to decode string s[i....j]
// base case
opt[0,0] = 1 , opt[i,j] = 0 for i > j
// iteration
opt[i,j] = s[j]!='0' ?opt[i,j-1]:0 + (s[j-1] == '1' || s[j-1] == '2' && s[j] <= '6')?opt[i,j-2]:0;

The below is the implementation, time complexity O(n^2) and space O(n^2) required.

 public class Solution {  
   public int numDecodings(String s) {  
     // edge case  
     if(s.length()==0) return 0;  
     // DP  
     int opt[][] = new int[s.length()][s.length()+1];  
     // base case  
     opt[0][0] = 1;  
     // iteration  
     for(int i = 1;i <= s.length();i++)  
       for(int j = 0;j+i <= s.length();j++)  
         opt[j][j+i] = ((s.charAt(j+i-1)!='0')?opt[j][j+i-1]:0) + ((i >=2 && (s.charAt(j+i-2)=='1' || s.charAt(j+i-2)=='2' && s.charAt(j+i-1)<='6'))?opt[j][j+i-2]:0);  
     return opt[0][s.length()];  
   }  
 }  

In the above code, I found out that the step is totally useless, opt[3][4] will never be used to compute opt[0][4]. So the final solution should be O(n) time and space.

 public class Solution {  
   public int numDecodings(String s) {  
     // edge case  
     if(s.length()==0) return 0;  
     // DP  
     int opt[] = new int[s.length()+1];  
     // base case  
     opt[0] = 1;  
     // iteration  
     for(int j = 1;j <= s.length();j++)  
       opt[j] = ((s.charAt(j-1)!='0')?opt[j-1]:0) + ((j >=2 && (s.charAt(j-2)=='1' || s.charAt(j-2)=='2' && s.charAt(j-1)<='6'))?opt[j-2]:0);  
     return opt[s.length()];  
   }  
 }  

It's really bad to write an algorithm without carefully think about dimension. The problem is a one -dimension problem, while the middle result may be useful. But in writing the algorithm on can clearly see that middle result is useless.

Improved Way: As usual, a 2D space can always be reduced to 1D when current result only rely on previous row/column. For this problem, current result only relies on previous two steps. We can reduced the space use to O(1).

 public class Solution {  
   public int numDecodings(String s) {  
     // edge case  
     if(s.length()==0) return 0;  
     // DP  
     int father = 1, grandpa = 1;  
     // base case  
     int opt = 1;  
     // iteration  
     for(int j = 1;j <= s.length();j++){  
       opt = ((s.charAt(j-1)!='0')?father:0) + ((j >=2 && (s.charAt(j-2)=='1' || s.charAt(j-2)=='2' && s.charAt(j-1)<='6'))?grandpa:0);  
       grandpa = father;  
       father = opt;  
     }  
     return opt;  
   }  
 }  

While, it's not the end, I finally find someone's post with an improved DFS approach. It's from mahdy,
he uses a map to store each path that has been visited. Each time we make the recursive call, visit the map first. That really brings the run time from O(2^n) to O(n)!

I'll just modify on my previous DFS code.

 public int numDecodings(String s) {  
     if(s == null || s.length() == 0) return 0;  
     Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
     map. put(s.length(), 1);  
     return dfs(s, 0, map);  
   }  
   private int dfs(String s, int index, Map<Integer, Integer> map){  
     // check path memory  
     if(map.containsKey(index)) return map.get(index);  
     // recursion  
     int count = 0;  
     if(index+1 < s.length() &&(s.charAt(index) == '1' || s.charAt(index) == '2' && s.charAt(index+1) <= '6'))  
       count += dfs(s, index+2, map);  
     if(s.charAt(index) != 0)  
       count += dfs(s, index+1, map);  
     map.put(index, count);  
     return count;  
   }