91. Decode Ways

Thinking:

• Method:
  • 通过动态规划实现。
  • 分析：
    • 通过一个长度为len + 1的数组装载每个位的结果。
    • dp[0]的值为1。
    • 每个当前值都是由dp[i - 1]和dp[i - 2]决定的。
      • 当前值在1-9之间，我们当前值加上dp[i - 1]。
      • 当这两位的值在10 - 26之间，就要加上dp[i - 2]。

class Solution {
    public int numDecodings(String s) {
        if(s == null) return 1;
        int len = s.length();
        int[] dp = new int[len + 1];
        dp[0] = 1;
        for(int i = 0; i < len; i++){
            char c = s.charAt(i);
            if(c > '0' && c <= '9') dp[i + 1] += dp[i];
            if(i > 0 && c >= '0' && c <= '6' && s.charAt(i - 1) == '2') dp[i + 1] += dp[i - 1];
            if(i > 0 && s.charAt(i - 1) == '1') dp[i + 1] += dp[i - 1];
        }
        return dp[len];
    }
}

二刷

这道题还是比较简单的DP，稍微想了一下就写出来了。

class Solution {
    public int numDecodings(String s) {
        if(s == null) return 0;
        int len = s.length();
        int[] dp = new int[len + 1];
        dp[0] = 1;
        char[] arr = s.toCharArray();
        for(int i = 1; i <= len; i++){
            int c = arr[i - 1] - '0';
            if(c > 0 && c <= 9) dp[i] += dp[i - 1];
            if(i > 1 && c >= 0 && c <= 6 && arr[i - 2] == '2') dp[i] += dp[i - 2];
            if(i > 1 && arr[i - 2] == '1') dp[i] += dp[i - 2];
        }
        return dp[len];
    }
}