思路及解法

暴力递归

假设⼀个字符是S，第⼀次拆解就有两种情况，然后分别对后⾯的部分分别译码，使⽤递归即可：

java

public class Solution46 { public int solve (String nums) { return recursion(nums.toCharArray(), 0); } public int recursion(char[] nums, int start){ if(start == nums.length){ return 1; } if(nums[start] == '0') return 0; // 使⽤⼀位字符译码 int count1 = recursion(nums,start+1); int count2 = 0; // 符合两位字符的译码 if((start < nums.length-1) && (nums[start] == '1' || (nums[start] == '2' &&nums[start+1] <= '6'))){ count2 = recursion(nums,start+2); } return count1 + count2; } }

但是上⾯的代码时间复杂度太⾼了，只要字符稍微⻓⼀点，运⾏时间就容易超过限制了：

记忆化递归

为了避免重复计算子问题，我们使用一个备忘录（memo）来存储已经计算过的结果。

java

class Solution { public int numDecodings(String s) { if (s == null || s.length() == 0) return 0; // 备忘录，初始化为-1表示未计算 Integer[] memo = new Integer[s.length()]; return dfs(s, 0, memo); } private int dfs(String s, int index, Integer[] memo) { // 基准情况1：成功解码到末尾，算作一种有效方法 if (index == s.length()) { return 1; } // 基准情况2：当前字符是'0'，无法解码，此路径无效 if (s.charAt(index) == '0') { return 0; } // 如果当前子问题已经计算过，直接返回结果 if (memo[index] != null) { return memo[index]; } int ways = 0; // 选择1：解码当前1位数字 ways += dfs(s, index + 1, memo); // 选择2：如果存在下一位，并且当前两位数字在10-26之间，则解码当前2位数字 if (index + 1 < s.length()) { int twoDigits = (s.charAt(index) - '0') * 10 + (s.charAt(index + 1) - '0'); if (twoDigits >= 10 && twoDigits <= 26) { ways += dfs(s, index + 2, memo); } } // 将结果存入备忘录 memo[index] = ways; return ways; } }

• 时间复杂度：O(n)，每个子问题最多被计算一次。
• 空间复杂度：O(n)，递归栈的深度和备忘录的空间

动态规划

将过程逆推，要想求得当前的字符串的译码类型，其实有两种，最后⼀个单独翻译，另外⼀种是倒数最后两个字符合起来翻译，这两者之和就是我们所要求的结果。

⽽要求前⾯的值，需要求更前⾯的值，最后⼀定会求得⼀个字符和两个字符的结果。其实这就是动态规划⾥⾯说的状态变化。递归其实就是逆推，这样会导致很多重复的计算。动态规划,则是从⼩数值计算到⼤数值。

既然我们知道是动态规划，定义 dp[i] 为数字串从左到右第i个数字结尾的当前数字串所拥有的翻译⽅法数，接着就需要找出状态转移⽅程：

• 如果 i=0 , dp[i]=1
• 否则
  • 如果nums[i]=0，说明需要和前⾯⼀个字符⼀起翻译
    • 如果i == 1，以10或者20开头， dp[i] = 1
    • 否则，数字串中存在10或者20的情况下，当前译码数等于后退两步的译码数， dp[i] =dp[i-2];
  • 否则，在符合字符范围内， dp[i]=dp[i-1]+dp[i-2]

java

class Solution { public int numDecodings(String s) { if (s == null || s.length() == 0 || s.charAt(0) == '0') { return 0; // 处理空串或以'0'开头的无效情况 } int n = s.length(); int[] dp = new int[n + 1]; // 初始化 dp[0] = 1; // 空字符串有一种解码方式（解码为空） dp[1] = 1; // 第一个字符只要不是'0'（前面已判断），就有1种解码方式 for (int i = 2; i <= n; i++) { int oneDigit = s.charAt(i - 1) - '0'; // 看最后一个字符（1位数字） int twoDigits = (s.charAt(i - 2) - '0') * 10 + oneDigit; // 看最后两个字符（2位数字） // 情况1：最后一个字符可以单独解码（必须是1-9） if (oneDigit >= 1 && oneDigit <= 9) { dp[i] += dp[i - 1]; } // 情况2：最后两个字符可以组合解码（必须是10-26） if (twoDigits >= 10 && twoDigits <= 26) { dp[i] += dp[i - 2]; } } return dp[n]; } }

• 时间复杂度：O(n)，需要遍历整个字符串一次。
• 空间复杂度：O(n)，用于存储dp数组。

空间优化动态规划（推荐）

观察上面的代码可以发现，计算dp[i]时只依赖于dp[i-1]和dp[i-2]。因此，我们可以不用维护整个数组，只用两个变量来滚动记录之前的状态即可，从而将空间复杂度优化到常数级别。

java

class Solution { public int numDecodings(String s) { if (s == null || s.length() == 0 || s.charAt(0) == '0') { return 0; } int n = s.length(); // 使用变量替代dp数组 int prevPrev = 1; // 对应于 dp[i-2]，初始化为dp[0]=1 int prev = 1; // 对应于 dp[i-1]，初始化为dp[1]=1 for (int i = 2; i <= n; i++) { int current = 0; int oneDigit = s.charAt(i - 1) - '0'; int twoDigits = (s.charAt(i - 2) - '0') * 10 + oneDigit; // 情况1：单独解码最后一个字符 if (oneDigit >= 1 && oneDigit <= 9) { current += prev; // 相当于 dp[i] += dp[i-1] } // 情况2：组合解码最后两个字符 if (twoDigits >= 10 && twoDigits <= 26) { current += prevPrev; // 相当于 dp[i] += dp[i-2] } // 滚动更新变量，为下一次迭代做准备 prevPrev = prev; prev = current; } return prev; } }