力扣|力扣 - 剑指 Offer 46. 把数字翻译成字符串力扣-剑指Offer46.把数字翻译成

题目剑指 Offer 46. 把数字翻译成字符串
思路1（递归，自顶向下）

这题和青蛙跳台阶很类似，青蛙跳台阶说的是青蛙每次可以跳一层或者两层，跳到第 n 层有多少种解法，而这题说的是讲数字翻译成字符串，每次可以翻译一个或者两个，但是翻译两个的时候还要判断是否为有效的，像 01、02 这种的数字就是无效的，同时超过 25 也是无效的，因此这些不能被翻译。然后我们可以得出状态转移方程：

\[dp[i] = \begin{cases} dp[i-1]+dp[i-2] & ,前两个数字组成的结果在10～25之间 \\ dp[i-1] & ,前面两个数字组成的结果是0开头的 \end{cases} \]

代码

class Solution { public int translateNum(int num) { if (num < 10) { return 1; }if (num % 100 >= 10 && num % 100 <= 25) { return translateNum(num/10) + translateNum(num/100); } else { return translateNum(num/10); } } }

复杂度分析

时间复杂度：\(O(2^N)\)，因为计算过的还是会被递归重复计算的，因此时间复杂度为\(O(2^N)\)
空间复杂度：\(O(N)\)

思路2（动态规划）

因为递归时间复杂度比较高，因此我们可以采用动态规划来解决这题，动态规划一般都是自底向上，利用 dp 数组存储利用之前计算过的数据。状态转移方程我们已经知道了，因此可以写代码了

代码

class Solution { public int translateNum(int num) { String str = String.valueOf(num); // 使用str.length()+1 int[] dp = new int[str.length()+1]; // 我们只能确定第一位有几种翻译方法 // 真正是从 1 开始，初始化 0 是用来来防止 i-2 出现 -1 的情况 dp[0] = 1; dp[1] = 1; for (int i = 2; i <= str.length(); i++) { // 如果是两位数的话，需要在10～25之间才有效，否则只能翻译一个数字 if (str.substring(i-2, i).compareTo("10") >= 0 && str.substring(i-2, i).compareTo("25") <= 0) { dp[i] = dp[i-1] + dp[i-2]; } else { dp[i] = dp[i-1]; } }return dp[str.length()]; } }

【力扣|力扣 - 剑指 Offer 46. 把数字翻译成字符串】同样我们可以优化下：

class Solution { public int translateNum(int num) { String str = String.valueOf(num); // 我们只能确定第一位有几种翻译方法 int a = 1; int b = 1; for (int i = 2; i <= str.length(); i++) { // 如果是两位数的话，需要在10～25之间才有效，否则只能翻译一个数字 if (str.substring(i-2, i).compareTo("10") >= 0 && str.substring(i-2, i).compareTo("25") <= 0) { int temp = a + b; a = b; b = temp; } else { a = b; } }return b; } }

复杂度分析