【每日算法Day 9】把数字翻译成字符串

看了下官方的解法，调用了API中的String.valueOf()将数字转为字符串，然后比较最后两位子串和"25"、"10"，时空间复杂度是一样的，不过代码简洁了不少。其实我一开始也想到了转为字符串，不过忽略了转换成字符串的数字也是可以按照字典序进行比较的，值得注意。

# 题目链接

LeetCode 面试题46. 把数字翻译成字符串 (opens new window)

# 题目描述

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

# 示例

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

1
2
3
4
5
6

# 解题思路

所有1位数字0~9可以被翻译成1个字符，2位数字中10~25可以被翻译成一个字符，除此之外没有别的数字组合能被翻译。记输入的数字位数为k（1<=k<10），将其每一位分别存储至长度为k的数组中。则能得到状态转移方程f(k)=f(k-1)+isValid*f(k-2)，f(1)=1,f(2)=1+isValid*1，其含义为长度为k的数组的翻译方法数可以拆分为两种情况：其长度为k-1的子数组能被翻译的方法数加上其后两位数字能够被翻译成字符时其长度为k-2的子数组能被翻译的方法数。根据该方程可以给出递归解法和动态规划解法。

# 递归解法

我提交的时候惊了，为什么递归解法执行用时和内存消耗都能击败100%的用户。。。

public class No46_TranslateNumToString {
    //转换数字到数组中
    public int translateNum(int num) {
        int length=0;
        int n=num;
        do {
            n/=10;
            length++;
        }while (n!=0);
        int[] array=new int[length];
        for (int i = length - 1; i >= 0; i--) {
            array[i]=num%10;
            num/=10;
        }
        return getResult(array,length);
    }

    //递归解法，也可以不传length而在递归时调用System.arrayCopy()传子数组
    public int getResult(int[] num,int length) {
        switch (length) {
            case 1:
                return 1;
            case 2:
                int value=num[0]*10+num[1];
                return (value > 9 && value < 26) ? 2 : 1;
            default:
                int last2num=num[length-2]*10+num[length-1];
                return (last2num > 9 && last2num < 26)?getResult(num,length-2)+getResult(num,length-1):getResult(num,length-1);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 动态规划

在LeetCode上这两种方法的执行用时都为0ms，内存消耗都为36.3MB，但理论上动态规划的方法更快。

//转换到数组方法同上
public int getResult(int[] num) {
    //1位或2位数字时直接返回结果
    switch (num.length) {
        case 1:
            return 1;
        case 2:
            int value = num[0] * 10 + num[1];
            return (value > 9 && value < 26) ? 2 : 1;
    }

    //3位以上时使用dp数组保存结果
    int[] dp=new int[num.length+1];
    dp[1]=1;
    int value = num[0] * 10 + num[1];
    dp[2]= (value > 9 && value < 26) ? 2 : 1;

    for (int i = 3; i < dp.length; i++) {
        int last2num=num[i-2]*10+num[i-1];
        dp[i]=(last2num > 9 && last2num < 26)?dp[i-2]+dp[i-1]:dp[i-1];
    }
    return dp[dp.length-1];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 总结

在使用动态规划时，由于循环中每次只需要使用相邻的两个量，则可以只用两个变量保存而不是用O(logn)大小的dp数组（称为滚动数组优化动态规划）。不过由于在前面将num转换为数组的过程中使用了长度为log(10,num)也即O(logn)大小的数组，空间复杂度仍为O(logn)。时间复杂度为O(logn)。

Wallace's Blog

Choose mode