「剑指 Offer 46. 把数字翻译成字符串」笔记

最近面试了国内互联网小厂的日常实习，他们出了一道这样的题目：

把数字翻译成字符串
有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。
现在给一串数字，返回有多少种可能的译码结果
示例1
输入
"12"
输出
2
说明
2种可能的译码结果（”ab” 或”l”）
示例2
输入
"31717126241541717"
输出
192
说明
192种可能的译码结果

其实和力扣剑指 Offer 46. 把数字翻译成字符串差不多，只是把范围改成[0,25]了，这道题有点像剑指 Offer 10- II. 青蛙跳台阶问题，只是前提需在两个位置时判断这个数是否符合[0,25]，然后在做取舍。

方法一

使用递归暴力方法做。

如果所示，

对于“2163”，从左边开始遍历，有“2”和“163”这一支，还有”21”和“63”这只分支。
然后指针到左子树则有”1”和“63”这一支，还有”16”和“3”这一支
依次递归

不难看出，从左边遍历和从右边遍历是等价的。

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

方法二

通过上图我们也可以看出，有重复计算的，因此可以使用备忘录储存优化一下。

class Solution {
    Map<Integer, Integer> map;
    public int translateNum(int num) {
        map = new HashMap<>();
        return dfs(num);
    }
    public int dfs(int num) {

        if (map.containsKey(num))
            return map.get(num);
        if (num < 10) {
            return 1;
        }
        if (num % 100 >= 10 && num % 100 <= 25) {
            int t1 = dfs(num / 100);
            int t2 = dfs(num / 10);
            map.put(num/100,t1);
            map.put(num/10,t2);
            return t1 + t2;
        }
        int t3 = dfs(num / 10);
        map.put(num/10,t3);
        return t3;
    }
}

方法三

动态规划法，dp数组的定义，dp[i] 意义为在下标i之前的所有的方法

如果截取的[i-2,i]的数字在[0,25]之内，那么状态转移方程为 dp[i] = dp[i-1]+dp[i-2]
否则dp[i] = dp[i-1]

class Solution{
    public int translateNum(int num){
        //动态规划法
        String s = String.valueOf(num);
        int[] dp = new int[s.length()+1];
        dp[0] = dp[1] = 1;

        for(int i = 2;i <= s.length();i++){
            if(s.substring(i-2,i).compareTo("10") >= 0 && s.substring(i-2,i).compareTo("25") <= 0){
                dp[i] = dp[i-2] + dp[i-1];
            }else{
                dp[i] = dp[i-1];
            }
        }
        return dp[s.length()];
    }
}

总结

使用记忆化递归的方法，除了根据暴力解法来进一步优化比较容易想到外，相对于动态规划，当你的子问题没有求解时，程序会自动去求解，而不需要小心翼翼的去确保顺序，减轻我们的工作量。记忆化递归相比于动态规划的劣势在空间上的优化比较困难，在面试或者刷题的时候，优先保证能求解出来，然后在做进一步的优化，所以记忆化递归在这方面比较有优势。