Question

link

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.

Stats

Frequency 4
Difficulty 3
Adjusted Difficulty 3
Time to use ----------

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;
}