题目描述

一个只包含 A-Z 的消息可以用如下方式编码成数字：

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，返回共有多少种解码方案。

样例

输入：”12”
输出：2
解释：它可以被解码成 “AB” (1 2) 或者 “L” (12)。

输入：”226”
输出：3
解释：它可以被解码成 “BZ” (2 26), “VF” (22 6),
或者 “BBF” (2 2 6)。

算法1

(一维dp) $O(n)$

状态表示：f[i] 表示前 i 个数字共有多少种解码方式。
初始化：0个数字解码的方案数1，即 f[0]=1。 注意：要大于0 时
状态转移：f[i] 可以表示成如下两部分的和：

如果第 i 个数字不是0，则 i 个数字可以单独解码成一个字母，此时的方案数等于用前 i−1 个数字解码的方案数，即 f[i−1]；
如果第 i−1个数字和第 i 个数字组成的两位数在 10 到 26 之间，则可以将这两位数字解码成一个字符，此时的方案数等于用前 i−2 个数字解码的方案数，即 f[i−2]；
时间复杂度分析：状态数是 n 个，状态转移的时间复杂度是 O(1)，所以总时间复杂度是 O(n)。

时间复杂度

参考文献

Java 代码

public int numDecodings(String s) {
        if (s == null || s.length() == 0) return 0;
        int n = s.length();
        int[] dp = new int[n];

        if(s.charAt(0) > '0')
        dp[0] = 1;

        for (int i = 1; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '1' && c <= '9') {
                dp[i] += dp[i - 1];
              }

            if (i >= 1 ) {
              int v = Integer.parseInt(s.substring(i-1, i+1));
                 System.out.println(v);
              if (v >= 10 && v <= 26) {
                  if (i == 1) dp[i]++;
                  else
                  dp[i] += dp[i - 2];
              }
            }
        }
        return dp[n - 1];
    }

算法2

(dfs + cache)

java 代码

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) return 0;
        Map<Integer, Integer> map = new HashMap<>();
        return dfs(s, 0, map);
    }
    // dfs means the decode ways from pos -> n
    private int dfs(String s, int pos, Map<Integer,Integer> map) {
        if (pos == s.length()) return 1;

        if (map.containsKey(pos)) {
            return map.get(pos);
        }

        if (s.charAt(pos) == '0') {
            map.put(pos, 0);
            return 0;
        }

        int res = dfs(s, pos + 1, map);
        if (pos < s.length() - 1) {
        int val = Integer.parseInt(s.substring(pos, pos + 2));
            if (val >= 10 && val <= 26) {
                res += dfs(s, pos + 2, map);
            }
        }
        map.put(pos, res);
        return res;
    }
}