91. Decode Ways

Problem:

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.

Analysis:

这道题非常重要，facebook经常考的。要做到用constant space熟练写出来。

State: dp[i], how many decode ways at char i - 1.

Transition: dp[i] depend on the current digit and last two digits. If last two digits qualifies the mapping then dp[i] = dp[i - 1] + dp[i -2]. Otherwise, dp[i] = dp[i - 1].

Example:

"1224"

        i

Current dp[i]  is the sum of substring "122" and substring “12”

Solution:

The case 0 is hard to implement. Thanks java, with the Integer.valueOf() function. We can remove the leading 0. If current digit is 0, we know that dp[current] is 0.  But we still need to update dp1, if last two digits qualifies. 

O(n) space:

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int len = s.length();
        int[] dp = new int[len + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;
        for(int i = 2; i <= len; i++) {
            int first = Integer.valueOf(s.substring(i - 1, i));
            int second = Integer.valueOf(s.substring(i - 2, i));
            if (1 <= first && first <= 9) {
                dp[i] += dp[i - 1];
            }
            if (10 <= second && second <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[len];
    }
}

O(1) space:

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) 
            return 0;
        int dp2 = 1;
        
        int dp1 = way(s.substring(0, 1));
        for (int i = 1; i < s.length(); i++) {
            int temp = dp1;
            dp1 = dp1 * way(s.substring(i, i + 1)) + dp2 * way(s.substring(i - 1, i + 1));
            dp2 = temp;
        }
        return dp1;
    }
    
    private int way(String code) {        
        int res = Integer.valueOf(code);
        if (1 <= res && res <= 9 && code.length() == 1) return  1;
        if (10 <= res && res <= 26 && code.length() == 2) return 1;
        return 0;
    }
}