7-005-(LeetCode- 91) 解码方法

arctic_fox / 2023-05-03 / 原文

1. 题目

读题

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

LeetCode 91题是一个动态规划的问题，要求计算给定一个只包含数字的非空字符串的解码方法的总数，其中每个数字可以对应一个字母，例如1对应A，2对应B，…，26对应Z。

考查点

这道题考查了动态规划的基本思想和技巧，以及字符串和数字之间的转换和判断。需要注意的是：

字符串可能包含前导零，例如"06"，这种情况下不能解码为"F"，因为"6"和"06"在映射中不等价。
字符串可能包含无法解码的数字，例如"30"或"01"，这种情况下需要返回0。
动态规划数组可以用两个变量代替，优化空间复杂度。

2. 解法

思路

了动态规划的方法，思路是这样的：

定义一个数组dp，dp[i]表示字符串前i个字符的解码方法数。
初始化dp[0] = 1，表示空字符串有一种解码方法。
遍历字符串，对于每个字符，有两种情况：
- 如果当前字符不是’0’，说明它可以单独解码为一个字母，那么dp[i] += dp[i-1]，表示当前字符的解码方法数等于前一个字符的解码方法数。
- 如果当前字符和前一个字符可以组成一个10到26之间的数字，说明它们可以一起解码为一个字母，那么dp[i] += dp[i-2]，表示当前字符的解码方法数等于前两个字符的解码方法数。
最后返回dp[n]，其中n是字符串的长度。

具体实现

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1]; // dp[i]表示字符串前i个字符的解码方法数
        dp[0] = 1; // 空字符串有一种解码方法
        for (int i = 1; i <= n; i++) {
            // 如果当前字符不是'0'，说明它可以单独解码为一个字母
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            // 如果当前字符和前一个字符可以组成一个10到26之间的数字，说明它们可以一起解码为一个字母
            if (i > 1 && s.charAt(i - 2) != '0') {
                int num = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
                if (num >= 10 && num <= 26) {
                    dp[i] += dp[i - 2];
                }
            }
        }
        return dp[n]; // 返回最后一个字符的解码方法数
    }
}