把数字翻译成字符串

Light丶Long

于 2023-02-09 15:22:01 发布

阅读量237

点赞数

分类专栏：力扣练习算法-动态规划文章标签： java 动态规划算法

本文链接：https://blog.csdn.net/lin140611/article/details/128953247

版权

力扣练习同时被 2 个专栏收录

18 篇文章

订阅专栏

算法-动态规划

5 篇文章

订阅专栏

该文章讨论了一个编程问题，即如何计算一个数字按照特定规则翻译成字符串的不同方法数。通过动态规划，可以计算出每个数字序列对应的组合数，从而得到整个数字的翻译方法总数。例如，数字12258有5种不同的翻译。解决方案涉及到检查每一对数字是否能组成10到25之间的数，进而更新组合计数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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

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

解题思路：

边界条件，数字小于10仅有一位时，有且仅有一种组合；

数字大于等于10小于26时，有两种组合方式，以22为例子，可为2，2和22两种组合；

数字大于26，小于100时，有且仅有一种组合，以26为例，只能为2，6的组合；

分析举例12258，从1开始遍历，依次将后面的数字加到目标数字temp中，得到五个数据，分别是1，12，122，1225，12258，当temp=1时，最大组合数为1，只有一种（1）；当temp=12时，最大组合数为2，分别是（1、2）和（12）；当temp=122时，最大组合数为3，分别是（1、2、2），（12、2），（1、22）；当temp=1225时，最大组合数为5，分别是（1、2、2、5），（12、2、5），（1、22、5），（1、2、25），（12、25）；当temp=12258时，最大组合数为5，分别是（1、2、2、5、8），（12、2、5、8），（1、22、5、8），（1、2、25、8），（12、25、8）；

分析规律，当最后两位数能组成大于10且小于26的数字组合时，当前的最大组合数就是前两个数据的最大组合数之和，得出动态方程arr[i] = arr[i - 1] + arr[i - 2]，否则就等于上一个数据的最大组合数，得出动态方程arr[i] = arr[i - 1];

推导之后只需根据边界条件判断当数字为两位数时，ar[1]是1还是2（参考思路2，3）,最终代码如下：

class Solution {
    public int translateNum(int num) {
        if(num < 10) return 1;
        if(num < 26) return 2;
        String str = String.valueOf(num);
        char[] arrs  = str.toCharArray();
        int length = arrs.length;
        if(length == 2) return 1;
        int[] temp = new int[length];
        temp[0] = 1;
        if(arrs[0] == '1' || (arrs[0] == '2' && arrs[1] >= '0' && arrs[1] <= '5')) {
            temp[1] = 2;
        }else {
            temp[1] = 1;
        }
        for(int i = 2;i < length;i++) {
            char cur1 = arrs[i - 1];
            char cur2 = arrs[i];
            if(cur1 == '1' || (cur1 == '2' && cur2 >= '0' && cur2 <= '5')) {
                temp[i] = temp[i - 1] + temp[i - 2];
            }else {
                temp[i] = temp[i - 1];
            } 
        }
        return temp[length - 1];
    }
}