【千字分析】剑指 Offer 46. 把数字翻译成字符串

  • 时间:
  • 浏览:
  • 来源:互联网

我是小张同学,立志用更简洁的代码做更高效的表达


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

示例 1:

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

提示:

0 <= num < 231

这是一道典型的动态规划题目。对于一个数 num[i],我们有两种选择:

只翻译自己;
和前面的数字组合翻译,前提是组合的数在 10 − 25 10-25 1025 之间。
我们可以用 d p ( i ) dp(i) dp(i) 表示前 i i i 个数字的翻译方法数。根据以上两种选择,我们进行如下分析:

*如果只翻译自己,比如 12345 12345 12345,如果 5 5 5 单独翻译,那么方法数与 1234 1234 1234 是一样的, d p ( i ) = d p ( i − 1 ) dp(i)=dp(i-1) dp(i)=dp(i1)
如果和前面的数字组合,比如 12351235,如果 3535 组合翻译,从两方面考虑:
35 35 35 看成一个整体,虽然加了 55 但是和没加是一样的,状态 d p ( i ) = d p ( i − 1 ) dp(i)=dp(i-1) dp(i)=dp(i1)
35 35 35 组合就意味着不能再组合了,相当于条件 1 1 1 中的单独翻译自己,方法数与 12 12 12 是一样的。这时 d p ( i ) = d p ( i − 2 ) dp(i)=dp(i-2) dp(i)=dp(i2)
以上两种情况相加即可。
故状态转移函数为:

d p ( i ) = { d p ( i − 2 ) + d p ( i − 1 ) 前面两个数在1–25之间 d p ( i − 1 ) e l s e dp(i)= \begin{cases} dp(i-2)+dp(i-1)& \text{前面两个数在1--25之间}\\ dp(i-1)& \text{$else$} \end{cases} dp(i)={dp(i2)+dp(i1)dp(i1)前面两个数在1–25之间else

再考虑边界条件:

d p ( 0 ) = d p ( 1 ) = 1 dp(0)=dp(1)=1 dp(0)=dp(1)=1

注意:条件 1 1 1 星号处不是 d p ( i ) = d p ( i − 1 ) + 1 dp(i)=dp(i-1)+1 dp(i)=dp(i1)+1。比如 12 12 12 如果 2 2 2 单独翻译, 12 12 12 只有一种翻译方法。

C++动态规划解法

class Solution {
public:
    int translateNum(int num) {
        string str = to_string(num);
        int len = str.size();
        if(len < 2) return len;
        vector<int> dp(len+1);
        dp[1] = 1;
        dp[0] = 1;
        for(int i = 2;i <= len;i++){
            int n = (str[i-2] - '0') * 10 + (str[i-1] - '0');
            if(n >= 10 && n <= 25) dp[i] = dp[i-2]+dp[i-1];
            else dp[i] = dp[i-1];
        }
        return dp[len];
    }
};


此外,还有一种更简洁的数字求余+递归方法

class Solution {
public:
    int translateNum(int num) {
        if(num > 9 && num < 26) return 2;
        else if(num < 100) return 1;

        if(num % 100 > 25 || num % 100 < 10) return translateNum(num/10);
        else return translateNum(num/10) + translateNum(num/100);
    }
};

本文链接http://metronic.net.cn/metronic/show-53461.html