91. Decode Ways Leetcode Java

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.

Solution:

Obviously it is a dynamic programming problem, but a little more work is needed. Because for different cases, the recursion equation will be different. For example, 123, res[3]=res[1]+res[2] because it can decoded by either 1+23 or 12+3. But for 128 there is only one possible decoded way: 12+8, (28 is not a valid code) thus res[3]=res[2].

There are some other possibilities: (x represent any digit char)

x00x -> not a valid code, return 0,(can't have 2 or more consecutive 0)

x30x -> not a valid code, return 0, (if num.charAt(i)=='0', num.charAt(i-1) can't greater than 2)

x20x or x10x if num.charAt(i)==0.res[i]=res[i-2], because the number can't start with 0.

x11x...x19x,x21x...x26x, res[i]=res[i-1]+res[i-2]

else res[i]=res[i-1]

Part of them follows Fibonacci series, some of them do not.

Time complexity: O(n), constant space.

 public int numDecodings(String s) {  
    if(s==null||s.length()==0 || s.charAt(0)=='0') return 0;  
    int pre=1;  
    int cur=1;  
    for(int i=1;i<s.length();i++){  
     if((s.charAt(i-1)-'0')*10+(s.charAt(i)-'0')<=26 && (s.charAt(i-1)-'0')*10+(s.charAt(i)-'0')>=10) {  
       if(s.charAt(i)=='0') {  
         cur=pre;  
       }  
       else{  
       int temp=cur;  
       cur+=pre;  
       pre=temp;  
       }  
     }  
     else if((s.charAt(i-1)=='0'|| s.charAt(i-1)>='3')&& s.charAt(i)=='0') return 0;  
     else {  
       pre=cur;  
     }  
    }  
    return cur;  
   }