剑指 Offer 46. 把数字翻译成字符串

LeetCode： 剑指 Offer 46. 把数字翻译成字符串

递归回溯 1.1 先是 +1 遍历每一位数 1.2 之后从后往前 +2 的形式拼接成两位数

动态规划 >> 没想到

递归回溯

想到了递归回溯，但不知道怎么下手， 确实没有想到这样的写法。

int ans = 0; public int translateNum(int num) { String s = String.valueOf(num); dfs(s, 0, s.length()); return ans; } public void dfs(String s, int index, int len){ if(index == len){ ans++; return ; } // 单个 dfs(s, index + 1, len); if(index + 2 <= len){ // 如果还能放两个 int temp = Integer.valueOf(s.substring(index, index + 2)); if(temp >= 10 && temp <= 25){ dfs(s, index + 2 , len); } } }

动态规划

使用滚动数组优化 dp 的空间

滚动数组： q 、p、r

public int translateNum(int num) { String s = String.valueOf(num); // 滚动数组 int q = 0, p = 0, r = 1; for (int i = 0; i < s.length(); i++) { q = p; p = r; r = 0; r += p; if(i == 0) continue ; // 截取前一个和当前的两个数组成两位数 int temp = Integer.valueOf(s.substring(i - 1, i + 1)); if(temp >= 10 && temp <= 25){ r += q; } } return r; }

---

>> 解题思路