Question

link

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

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is easy to think, but hard to write.

Why? Because there are a lot of cases that the decode ways = 0. For example, input = “02” or “50”. We must handle those cases well. Also, boundary cases can cause some trouble.

Solution

DP solution, the transformation function is:

Count[i] = Count[i-1] if only S[i-1] is valid

Count[i] = Count[i-1] + Count[i-2] if S[i-1] and S[i-2] both valid

Code

First, my code.

public int numDecodings(String s) {
    int len = s.length();
    if (len == 0) return 0;
    // now len >= 1
    int[] dp = new int[len];
    if (s.charAt(0) == '0') dp[0] = 0;
    else dp[0] = 1;
    if (len == 1) return dp[0];
    // now len >= 2
    for (int i = 1; i < len; i ++) {
        if (s.charAt(i) != '0') dp[i] += dp[i-1];
        int doubleDigit = Integer.parseInt(s.substring(i-1, i+1));
        if (s.charAt(i-1) != '0' && 1 <= doubleDigit && doubleDigit <= 26)
            if (i != 1) dp[i] += dp[i-2];
            else dp[i] += 1;
    }
    return dp[len - 1];
}

Second, code from this blog.

The only difference is an additional ‘1’ at position 0 of the dp array. This helps simply the code a lot!

public int numDecodings(String s) {  
    int n = s.length();  
    if (n==0) return 0;  
    int[] dp = new int[n+1];  
    dp[0] = 1;  
    if (isValid(s.substring(0,1))) dp[1] = 1;  
    else dp[1] = 0;  
    for(int i=2; i<=n;i++){  
        if (isValid(s.substring(i-1,i)))  
            dp[i] = dp[i-1];  
        if (isValid(s.substring(i-2,i)))  
            dp[i] += dp[i-2];  
    }  
    return dp[n];  
}  

public boolean isValid(String s){  
    if (s.charAt(0)=='0') return false;  
    int code = Integer.parseInt(s);  
    return code>=1 && code<=26;  
}