题目地址

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

题目描述

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

题目数据保证答案肯定是一个 32 位的整数。



示例 1：

输入："12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2：

输入："226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3：

输入：s = "0"
输出：0
示例 4：

输入：s = "1"
输出：1
示例 5：

输入：s = "2"
输出：1


提示：

1 <= s.length <= 100
s 只包含数字，并且可以包含前导零。

题解

动态规划

• 定义状态：

dp[i] = s[0..i) 解码的总数

状态转移方程：

• case 1 当前数不为 0，那么可以走一步，即把当前位置的数字添加到状态中。也就是从状态 s[0..i) 转移到 s[0..i+1)。代码如下所示：

if (s.charAt(i) != '0') {
    dp[i+1] += dp[i];
}

• case 2 两个数合起来小于 26，那么可以走两步，即把当前位置和下一个位置的数字添加到状态中。也就是从状态 s[0..i) 转移到 s[0..i+2)。代码如下所示：

if (i+1 < s.length() && (s.charAt(i) == '1' 
                     || (s.charAt(i) == '2' && s.charAt(i+1) <= '6'))) {
    dp[i + 2] += dp[i];
}

接下来让我们考虑 base case。

base case 可以看成一个出发点，从这个出发点转移到 s[0..n)，n 为字符串 s 的长度，一共有多少种转移路径，其路径总数相当于解码的总数。

因此我们可以定义一个起点，s[0..0)，因为我们要算路径，所以初始值要赋为 1。

dp[0] = 1;

完整代码如下所示：

class Solution {
    public int numDecodings(String s) {
        // dp[i] = s[0..i) 解码的总数
        int[] dp = new int[s.length() + 2];

        // base case
        // s[0, 0) 表示起始点，可以从起始点走到的都算一条路径
        dp[0] = 1;

        for (int i = 0; i < s.length(); ++ i) {
            // case 1 当前数不为 0，那么可以走一步
            // 路径： s[0..i) ==> s[0..i+1)
            if (s.charAt(i) != '0') {
                dp[i+1] += dp[i];
            }

            // case 2 两个数合起来小于 26，那么可以走两步
            // 路径：s[0..i) ==> s[0..i+2)
            if (i+1 < s.length() && (s.charAt(i) == '1' 
                                 || (s.charAt(i) == '2' && s.charAt(i+1) <= '6'))) {
                dp[i + 2] += dp[i];
            }
        }

        // 结果
        // n = s.length()
        // dp[n] = s[0..n) 解码的总数
        return dp[s.length()];
    }
}

上面的转移方向是：

• 走一步：dp[i] ==> dp[i+1]
• 走两步：dp[i] ==> dp[i+2]

换一种状态转移方向

• 走一步：dp[i-1] ==> dp[i]
• 走两步：dp[i-2] ==> dp[i]

class Solution {
    public int numDecodings(String s) {
        // dp[i] = s[0..i) 解码的总数
        int[] dp = new int[s.length() + 2];

        // base case
        // s[0, 0) 表示起始点，可以从起始点走到的都算一条路径
        dp[0] = 1;

        for (int i = 1; i <= s.length(); ++ i) {
            // case 1 当前数不为 0，那么可以走一步
            // 路径： s[0..i) ==> s[0..i+1)
            if (s.charAt(i-1) != '0') {
                dp[i] += dp[i-1];
            }

            // case 2 两个数合起来小于 26，那么可以走两步
            // 路径：s[0..i) ==> s[0..i+2)
            if (i-2 >= 0 && (s.charAt(i-2) == '1' 
                                 || (s.charAt(i-2) == '2' && s.charAt(i-1) <= '6'))) {
                dp[i] += dp[i-2];
            }
        }

        // 结果
        // n = s.length()
        // dp[n] = s[0..n) 解码的总数
        return dp[s.length()];
    }
}

这样也是可以的。