题解 | 把数字翻译成字符串

1、解题思路

1. 动态规划：定义 dp[i] 为前 i 个数字可以解码的方式数。递推关系： 如果当前数字 s[i] 不是 '0'，则可以单独解码，dp[i] += dp[i-1]。如果前两个数字 s[i-1] 和 s[i] 组成的数字在 10 到 26 之间，则可以组合解码，dp[i] += dp[i-2]。初始条件： dp[0] = 1（空字符串有一种解码方式）。dp[1] = 1（如果第一个字符不是 '0'）。
2. 边界条件：如果字符串以 '0' 开头，直接返回 0（无法解码）。如果字符串中有 '0' 但前面无法组合（如 '30'），则直接返回 0。
3. 空间优化：使用两个变量 prev 和 curr 代替 dp 数组，将空间复杂度降为 O(1)。

2、代码实现

C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        // write code here
        if (nums.empty() || nums[0] == '0') {
            return 0;
        }

        int n = nums.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; ++i) {
            if (nums[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            int two_digits = stoi(nums.substr(i - 2, 2));
            if (two_digits >= 10 && two_digits <= 26) {
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // write code here
        if (nums.isEmpty() || nums.charAt(0) == '0') return 0;
        int n = nums.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            if (nums.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            int two_digits = Integer.parseInt(nums.substring(i - 2, i));
            if (two_digits >= 10 && two_digits <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 解码
# @param nums string字符串 数字串
# @return int整型
#
class Solution:
    def solve(self , nums: str) -> int:
        # write code here
        if not nums or nums[0] == '0':
            return 0
        n = len(nums)
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            if nums[i-1] != '0':
                dp[i] += dp[i-1]
            two_digits = int(nums[i-2:i])
            if 10 <= two_digits <= 26:
                dp[i] += dp[i-2]
        return dp[n]

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。
• 空间复杂度：O(n)，用于存储 dp 数组。