LeetCode刷题【剑指 Offer 46】把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

提示：

• 0 <= num < 231

带注解，动态规划

动态规划题，其实思路还是比较简单的，只是当中的if/else判断条件啰嗦了点，算不上复杂

把各种情况都理清楚的话，本题还是相当好解的

1. 当前数字独立成字母
2. 如果前面是0或者大于2，当前数字只能独立成字母
3. 如果前面数字是1，当前数字可以独立成字母，也可以和前面的1组成字母
4. 如果前面的数字是2，如果当前数字小于等于5，可以独立成字母，也可以和前面的1组成字母
5. 如果前面的数字是2，如果当前数字大于5，当前数字只能独立成字母

各种情况的数量

1. 当前数字独立成字母的时候。数量继承dp[i-1]
2. 和前一位数字组成字母的时候，数量为 “独立成字母的dp[i-1]” + “和前一位组成字母的时候继承的前前一位的dp[i-2]”
3. 如果dp[i-2]不存在，不妨简单假设个情况25，应当是 [2,5] + [25]两种情况，那么可知不存在的时候的dp[i-2]的值应当为1
4. 初始边界条件一个数字的时候只能为1，即dp[0] = 1

class Solution {
    final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
            99999999, 999999999, Integer.MAX_VALUE };

    public int translateNum(int num) {
        if (num<10){
            return 1;
        }
        int size = numSize(num);
        //构建 num数字拆分出来的数组，便于用下标处理
        int[] arr = new int[size];
        int idx = arr.length;
        while (num > 0){
            arr[--idx] = num % 10;
            num /= 10;
        }
        int[] dp = new int[size];
        dp[0] = 1;
        while (++idx < size){
            //如果前一位是0，或者前一位大于2，当前位置只能独立组成字母
            if (arr[idx-1] == 0 || arr[idx-1]>2){
                dp[idx] = dp[idx-1];
                continue;
            }
            //如果前一位为1，当前位置可以和前一位组成  1X  表示一个字母，那么当前位置可以组成的情况为
            // 当前位置单独成字母的情况  dp[idx-1]  加上  和前一位一起组成字母的情况  dp[idx-2]
            if (arr[idx-1] == 1){
                dp[idx] = dp[idx-1] + (idx>1?dp[idx-2]:1);
                continue;
            }
            //如果前一位为2，
            if (arr[idx-1] == 2){
                if (arr[idx] > 5){
                    //如果当前位置大于5，只能独立成字母
                    dp[idx] = dp[idx-1];
                }else{
                    //如果当前位置小于等于5，可以和前一位组成一个新字母
                    dp[idx] = dp[idx-1] + (idx>1?dp[idx-2]:1);
                }
            }
        }
        return dp[dp.length-1];
    }

    public int numSize(int num){
        int i = -1;
        while (++i < sizeTable.length){
            if (sizeTable[i] >= num){
                return i+1;
            }
        }
        return -1;
    }
}

本题和91. 解码方法是一样的，我还记得当初第一次做91的时候时候要命的提交了十多次，隔了两个月现在这题也能一次通过了。

都没啥问题的话可以再尝试下639 解码方法 II