📃 题目描述

题目链接：

• 剑指 Offer 46. 把数字翻译成字符串 (opens new window)
• BM69 把数字翻译成字符串 (opens new window)

🔔 解题思路

dp[i] 表示字符串 nums 中以 i 个位置结尾的前缀字符串的解码种数，例如 nums = "123", 此时dp[0]=1,dp[1]=2,dp[2]=3

• 当前字符不等于 0 的时候, dp[i] = dp[i-1], 此时将当前位置的一个字符译码
• 当前字符+前一个字符，记为num, 如果 10<=num<=26，此时符合两个合并一起译码的条件，dp[i] = dp[i - 2]

总的来说，其实这道题目很像爬楼梯，一次能爬一层和爬两层，只是爬的过程中增加了一些限定条件，只要将这些限定条件屡清楚则可以完全搞懂这类题目~

import java.util.*;


public class Solution {
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        if (nums == null || nums.length() == 0 || nums.charAt(0) == '0') {
            return 0;
        }
        
        int n = nums.length();
        // dp[i] 表示 nums[0...i] 有多少种译码结果
        int[] dp = new int[n];
        dp[0] = 1;
        
        for (int i = 1; i < n; i ++) {
            // 1. 最基本的, nums[i] 单独编码
            if (nums.charAt(i) != '0') {
                dp[i] = dp[i - 1];
            }
            
            // 2. nums[i] 和 nums[i - 1] 共同编码
            int num = (nums.charAt(i - 1) - '0') * 10 + (nums.charAt(i) - '0');
            if (num >= 10 && num <= 26) {
                // 处理下边界情况
                if (i == 1) {
                    dp[i] += 1;
                }
                else {
                    dp[i] += dp[i - 2];
                }
            }
        }
        
        return dp[n - 1];
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：