小学生都能看懂的题解 | #把数字翻译成字符串#

问题理解

我们要把一个由数字组成的字符串解码成字母。例如：

'1' 解码成 'a'
'2' 解码成 'b'
...
'26' 解码成 'z'

给定一个数字字符串，比如 "12"，我们想知道有多少种不同的方式把这个字符串解码成字母。

对于 "12"，可以解码成：

'1' 和 '2' -> 'a' 和 'b' -> "ab"
'12' -> 'l' -> "l"

所以 "12" 有 2 种解码方式。

解题思路

我们用动态规划来解决这个问题。想象一下我们有一个盒子，盒子里存放了解码的结果数量。我们一步一步地往盒子里加更多的结果。

初始化：
- 设定一个数组 dp，dp[i] 代表前 i 个字符的解码方式数量。
- dp[0] 是 1，表示没有字符的情况有一种方式（什么都不做）。
- dp[1] 是 1，如果第一个字符不是 '0'，它就有一种解码方式。
逐步计算：
- 从第二个字符开始（即 i = 2），我们检查每个字符：
  - 如果当前字符单独可以解码（即它的值在 1 到 9 之间），那么它的解码方式就等于前一个字符的解码方式（即 dp[i] += dp[i-1]）。
  - 如果前两个字符组合在一起可以解码（即它的值在 10 到 26 之间），那么它的解码方式就等于前两个字符的解码方式（即 dp[i] += dp[i-2]）。
最后结果：
- 当我们处理完所有字符后，dp[n] 就是整个字符串的解码方式数量。

代码示例

以下是我们解决这个问题的代码：

public int solve(String nums) {
    int n = nums.length();
    
    // 如果字符串为空或第一个字符是'0'，则没有解码方式
    if (n == 0 || nums.charAt(0) == '0') return 0; 

    // 创建一个数组 dp，长度为 n + 1
    int[] dp = new int[n + 1];
    dp[0] = 1; // 空字符串的解码方式数量
    dp[1] = 1; // 第一个字符的解码方式数量

    for (int i = 2; i <= n; i++) {
        // 取出当前字符
        int oneDigit = Integer.parseInt(nums.substring(i - 1, i)); // 当前字符
        // 取出当前和前一个字符
        int twoDigits = Integer.parseInt(nums.substring(i - 2, i)); // 两个字符

        // 如果当前字符可以解码
        if (oneDigit >= 1 && oneDigit <= 9) {
            dp[i] += dp[i - 1]; // 把前一个结果加到当前
        }

        // 如果前两个字符可以解码
        if (twoDigits >= 10 && twoDigits <= 26) {
            dp[i] += dp[i - 2]; // 把前两个结果加到当前
        }
    }

    // 返回最后的解码方式数量
    return dp[n];
}

逐行解释

public int solve(String nums)：这是我们的方法，输入是一个数字字符串 nums。
int n = nums.length();：获取字符串的长度。
检查特殊情况：
- 如果字符串为空或第一个字符是 '0'，则直接返回 0，因为没有解码方式。
创建一个数组 dp：
- dp 的大小是 n + 1，用来存储每一步的解码方式数量。
- dp[0] = 1 表示没有字符时的解码方式数量。
- dp[1] = 1 表示第一个字符的解码方式数量。
for (int i = 2; i <= n; i++)：从第二个字符开始逐步计算。
解析单个和两个字符：
- oneDigit 是当前字符。
- twoDigits 是前两个字符组成的数字。
更新 dp[i]：
- 如果单个字符可以解码，dp[i] 加上前一个结果。
- 如果两个字符可以解码，dp[i] 加上前两个结果。
返回结果：
- 最后返回 dp[n]，就是整个字符串的解码方式数量。