LeetCode 91. Decode Ways

[Woodyiiiiiii]

A message containing letters from A-Z is being encoded to numbers using the following mapping:

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

Given a non-empty string containing only digits, determine the total number of ways to decode it.

The answer is guaranteed to fit in a 32-bit integer.

Example 1:

Input: s = "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "0"
Output: 0
Explanation: There is no character that is mapped to a number starting with '0'. 
We cannot ignore a zero when we face it while decoding. So, each '0' should be part of "10" --> 'J' or "20" --> 'T'.

Example 4:

Input: s = "1"
Output: 1

---

这道题实际上是遍历字符串然后递归求解的问题，一开始我试图用DFS递归的方法来做，显然Time Exceed：

// dfs and backtracking method:
class Solution {
    public int numDecodings(String s) {
        return dfs(s, 0);
    }
    public int dfs(String s, int i) {
        if (i >= s.length()) {
            return 1;
        }else if (s.charAt(i) == '0') {
            return 0;
        }
        int m1 = dfs(s, i + 1), m2 = 0;
        if (i + 1 < s.length() && (Integer.valueOf(s.substring(i, i + 2)) <= 26)
            && (Integer.valueOf(s.substring(i, i + 2)) > 0)) {
            m2 = dfs(s, i + 2);
        }
        return m1 + m2; 
    }
}

可以优化成DP解法，发现每个子问题的求解都是由前两个子问题的结果得来的(后效性？)，对一个子问题分析，可知当前字符串位置的Decode方法是由前一个位置和前二个位置(满足条件)的方法之和：

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int pre = s.charAt(0) == '0' ? 0 : 1, ppre = pre, cur;
        for (int i = 1; i < n; ++i) {
            int val = Integer.valueOf(s.substring(i - 1, i + 1));
            int sum1 = 0, sum2 = 0;
            if (val <= 26 && val >= 10) {
                sum1 = ppre;   
            }
            if (s.charAt(i) != '0') {
                sum2 = pre;
            }
            cur = sum1 + sum2;
            int tmp = pre;
            pre = cur;
            ppre = tmp;
        }
        return pre; 
    }
}

---

参考资料：

• https://leetcode.com/problems/decode-ways/