把数字翻译成字符串
dfs
-
解题思路：
![]( "把数字翻译成字符串")
- 翻译 2163 可以分解成：翻译 2 和剩下的 163 、翻译 21 和剩下的 63：
- 每次都有 2 种选择：翻译 1 个数、或 2 个数；
- 但如果该两位数没有对应的字母，翻译 2 个数这个选项就需要被砍掉；
- 指针从左往右扫描，画出下图，2 种选择对应 2 个分支，1 种选择对应 1 个分支；
-
复杂度：
- 时间复杂度：O(2^n)，每个节点都要遍历，栈的深度 n ，n 是数字字符个数；
- 空间复杂度：O(n)，栈的深度 n，n 是数字字符个数；
-
代码实现：
function translateNum(num: number): number { const dfs = (str: string, inx: number) => { // 指针抵达边界和超出边界返回 1 if (inx >= str.length - 1) return 1; // 计算该 2 位数 const sum = Number(str[inx] + str[inx + 1]); // 和在 [10,25] 之间可以直译 if (sum >= 10 && sum <= 25) { // 2 个分支的结果相加 return dfs(str, inx + 1) + dfs(str, inx + 2); } else { // 返回 1 个分支的结果 return dfs(str, inx + 1); } } return dfs(num.toString(), 0); };
dfs+缓存
-
解题思路：
![]( "把数字翻译成字符串")
- 黄色、蓝色阴影所标注的是重复的子树；
- 该递归优先遍历左子树，在右侧遇到重复子树时，没有必要重新计算；
- 计算过的结果用一个备忘录存下来，再遇到就直接拿来用；
-
图解：
![]( "把数字翻译成字符串")
-
复杂度：
- 时间复杂度：O(n)，栈的深度 n，n 是数字字符个数；
- 空间复杂度：O(n)，栈的深度 n，n 是数字字符个数；
-
代码实现：
function translateNum(num: number): number { const str = num.toString(); const n = str.length; const memo = new Array(n).fill(0); memo[n - 1] = 1; memo[n] = 1; const dfs = (str: string, inx: number, memo: Array<number>) => { // 之前存过，直接拿来用 if (memo[inx]) return memo[inx]; // 计算该 2 位数 const sum = Number(str[inx] + str[inx + 1]); // 和在 [10,25] 之间可以直译 if (sum >= 10 && sum <= 25) { // 2 个分支的结果相加 memo[inx] = dfs(str, inx + 1, memo) + dfs(str, inx + 2, memo); } else { // 返回 1 个分支的结果 memo[inx] = dfs(str, inx + 1, memo); } return memo[inx]; }; return dfs(str, 0, memo); };
动态规划
-
解题思路：
- 类似于爬楼梯；
- 第一个数字：一种翻译方法；
- 第二个数字：两数之和在 [10，25] 之间，则有两种翻译方法；
- 第 n 个数字：从第 n-1 个数字翻译一个数字或从第 n-2 个数字开始翻译两个数字；
- 递推公式： f(n) = f(n-1) + f(n-2)；
-
图解：
![]( "把数字翻译成字符串")
-
复杂度：
- 时间复杂度：O(N)，N 为字符串 s 的长度（即数字 num 的位数 log(num)），其决定了循环次数；
- 空间复杂度：O(N)，字符串 s 使用 O(N) 大小的额外空间；
-
代码实现：
function translateNum(num: number): number { const str: string = num.toString(); const n: number = str.length; const dp: Array<number> = new Array(n + 1); dp[0] = 1; dp[1] = 1; for (let i = 2; i < n + 1; i++) { const sum = Number(str[i - 2] + str[i - 1]); if (sum >= 10 && sum <= 25) { dp[i] = dp[i - 1] + dp[i - 2]; } else { dp[i] = dp[i - 1]; } } // 翻译前 n 个数的方法数 return dp[n]; };
打赏作者
您的打赏是我前进的动力
微信
支付宝
剑指 Offer 48.最长不含重复字符的子字符串
上一篇
评论
