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.

In this problem, you should consider many cases, and some of them are tricky.

1. If there is one digit, then it's obvious. If the digit is not equal to 0, we have only one way to decode. If the digit is 0, we have no ways to decode.

2. If the number has two digits. You should consider
10: 1 way,
11-19 : 2 ways,
20: 1 way,
21-26: 2 ways,
27-29: 1 way
30,40,50,...,90: 0 way
31-39, 41-49,...,91-99: 1 way

3. If the number has len>=3 digits or more, the number is
1) the first digit starts with 0,
   decodeWays=0;
2) the first two digits are from 11 to 19 or 22 to 26
decodeWays(x)=decodeWays(1 digit after x)+  decodeWays(2 digits after x)
3) the first two digits are others
decodeWays(x)=decodeWays(1 digit after x)

After considering these trivial cases, you can start coding. But, keep in mind that the recursion call is very expensive. I tried the first time using recursion, then the time limit exceeded.

Then I use DP to store the intermediate decodeWays. Keeping these values, recursion is avoided.

Java: DecodeWays

public int numDecodings(String s) {
   if(s.length()<1)
       return 0;
 
   char[]str=s.toCharArray();
 
   int[]decodeWays=new int[str.length];
   int last=str.length-1;
   if(str[last]-'0'==0)
       decodeWays[last]=0;
   else
       decodeWays[last]=1;
   if(last>=1)
   {
       if(str[last-1]-'0'>2)
       {
           if(str[last]-'0'==0)
               decodeWays[last-1]=0;
           else
               decodeWays[last-1]=1;
       }
       else if(str[last-1]-'0'==2)
       {
           if(str[last]-'0'>6)
               decodeWays[last-1]=1;
           else if(str[last]-'0'==0)
               decodeWays[last-1]=1;
           else
               decodeWays[last-1]=2;
       }
       else if(str[last-1]-'0'==1)
       {
           if(str[last]-'0'==0)
               decodeWays[last-1]=1;
           else
               decodeWays[last-1]=2;
       }
       else
       {
           decodeWays[last-1]=0;
       }
   }
 
   if(last>=2)
   {
       for(int i=last-2;i>=0;i--)
       {
           if(str[i]-'0'==0)
               decodeWays[i]=0;
           else
           {
               int ways=0;
               if(str[i]-'0'<2||(str[i]-'0'==2 && str[i+1]-'0'<=6))
                   ways=1;
               decodeWays[i]=decodeWays[i+1]+ways*decodeWays[i+2];
           }
       }
   }
 
   return decodeWays[0];      
 
}