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

题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。
一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示：
0 <= num < 231

转自：
作者：jyd
链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/mian-shi-ti-46-ba-shu-zi-fan-yi-cheng-zi-fu-chua-6/
           

题目分析，动态规划

记数字 num 第 i 位数字为 xi ，数字 num 的位数为 n ；例如： num=12258 的 n=5 , x1 =1 。(我们认为nums[0]是第一位);
状态定义： 设动态规划列表 dp，dp[i]代表以xi为结尾的数字的翻译方案数量。
转移方程： 若 xi和xi−1组成的两位数字可以被翻译，则dp[i]=dp[i−1]+dp[i−2] ；否则 dp[i]=dp[i−1] 。
始状态： dp[0] = dp[1] = 1 ，即 “无数字” 和 “第 1 位数字” 的翻译方法数量均为 1；
返回值： dp[n] ，即此数字的翻译方案数量。
Q： 无数字情况 dp[0]=1 从何而来？
A： 当 num第 1, 2位的组成的数字∈[10,25] 时，显然应有 2 种翻译方法，即 dp[2] = dp[1] + dp[0] = 2，而显然 dp[1] = 1，因此推出 dp[0] = 1 。
           

状态压缩，dp[i]只与dp[i-1]和dp[i-2]有关，所以采用两个数字即可。

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int a = 1, b = 1;
        for(int i = 2; i <= s.length(); i++) {
            String tmp = s.substring(i - 2, i);
            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
}
           

对称性。操作不涉及字符串的变化，并且dp数组含义不发生改变，所以对称性满足。其实仔细想一想就好了。

此题的动态规划计算是 对称的 ，即 从左向右 遍历（从第 dp[2] 计算至 dp[n]）和 从右向左 遍历（从第 dp[n−2] 计算至 dp[0]）所得方案数一致。从右向左遍历的代码如下所示。

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int a = 1, b = 1;
        for(int i = s.length() - 2; i > -1; i--) {
            String tmp = s.substring(i, i + 2);
            //compareTo源码就是判断大小。
            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
}
           

方法二：数字求余，既然对称性满足，那么从右到左判断即可。

上述方法虽然已经节省了 dp 列表的空间占用，但字符串 s 仍使用了 O(N) 大小的额外空间。
空间复杂度优化：
利用求余运算 num%10 和求整运算 num//10 ，可获取数字 num 的各位数字（获取顺序为个位、十位、百位…）。
因此，可通过 求余 和 求整 运算实现 从右向左 的遍历计算。而根据上述动态规划 “对称性” ，可知从右向左的计算是正确的。
自此，字符串 s 的空间占用也被省去，空间复杂度从 O(N) 降至 O(1)。
           

class Solution {
    public int translateNum(int num) {
        int a = 1, b = 1, x, y = num % 10;
        while(num != 0) {
            num /= 10;
            x = num % 10;
            int tmp = 10 * x + y;
            int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
            b = a;
            a = c;
            y = x;
        }
        return a;
    }
}