剑指offer-70、把数字翻译成为字符串

题⽬描述有⼀种将字⺟编码成数字的⽅式a-1, b-2, ... , z-26。现在给⼀串数字返回有多少种可能的译码结果示例1输⼊12返回值2说明2种可能的译码结果”ab” 或”l”示例2输⼊31717126241541717返回值192说明192种可能的译码结果仔细观察就会发现上⾯的编码从 1 到 26也就是可能⼀次译码使⽤是 1 位也可能是⼀次译码⽤了 2位⽐如 12 可以第⼀次⽤ 12 分开分别译码也可以把 12 合并起来进⾏译码。思路及解法暴力递归假设⼀个字符是S第⼀次拆解就有两种情况然后分别对后⾯的部分分别译码使⽤递归即可javapublic 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,start1); int count2 0; // 符合两位字符的译码 if((start nums.length-1) (nums[start] 1 || (nums[start] 2 nums[start1] 6))){ count2 recursion(nums,start2); } return count1 count2; } }但是上⾯的代码时间复杂度太⾼了只要字符稍微⻓⼀点运⾏时间就容易超过限制了记忆化递归为了避免重复计算子问题我们使用一个备忘录memo来存储已经计算过的结果。javaclass 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个数字结尾的当前数字串所拥有的翻译⽅法数接着就需要找出状态转移⽅程如果 i0 , 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]javaclass 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]。因此我们可以不用维护整个数组只用两个变量来滚动记录之前的状态即可从而将空间复杂度优化到常数级别。javaclass 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; } }