首页 > 试题广场 >

把数字翻译成字符串

[编程题]把数字翻译成字符串

热度指数：168709 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。

现在给一串数字，返回有多少种可能的译码结果

数据范围：字符串长度满足 $0 < n \leq 90$

进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

"12"

输出

说明

2种可能的译码结果（”ab” 或”l”）

示例2

输入

"31717126241541717"

输出

说明

192种可能的译码结果

算法知识视频讲解

Java

人间水长东

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // write code here

        // 算法核心思想：从0到n，以n为出口的记忆化搜索

        // dp[i] - 表示从第i字符到结尾，总共有dp[i]种译法
        int[] dp = new int[nums.length() + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = -1;
        }


        return process(nums, 0, dp);
    }

    public int process (String nums, int i, int[] dp) {
        int n = nums.length();
        // 递归出口
        if (i == n) {
            dp[i] = 1;
            return dp[i];
        }

        // 递归分支
        if (dp[i] != -1) {
            return dp[i];
        }
        // 可以只译当前一位数，也可以尝试译两位数

        // 先尝试只译一位数
        int num = Integer.parseInt(nums.substring(i, i + 1));
        int one = 0;
        if (num != 0) {
            // 注意非0
            if (dp[i + 1] == -1) {
                dp[i + 1] = process(nums, i + 1, dp);
            }
            one = dp[i + 1];
        }

        // 再尝试译两位数
        int two = 0;
        if (i < n - 1 && num != 0) {
            // 确保不越界，且不以0开头
            num = Integer.parseInt(nums.substring(i, i + 2));
            if (num > 0 && num <= 26) {
                // 合法字母
                if (dp[i + 2] == -1) {
                    dp[i + 2] = process(nums, i + 2, dp);
                }
                two = dp[i + 2];
            }
        }

        // 计算结果
        dp[i] = one + two;
        return dp[i];
    }
}

发表于 2024-09-24 01:37:04 回复(0)

Java

牛客499848474号

dp，但是时间复杂度是O(n^2)😅

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // write code here
        if(nums == null || nums.length() == 0) {
            return 0;
        }
        int[] ways = new int[nums.length() + 1];
        ways[0] = 1;
        for (int i = 1; i < ways.length; i++) {
            int count = 0;
            for (int j = Math.max(0, i - 2); j < i; j++) {
                if (nums.charAt(j) != '0' && Integer.valueOf(nums.substring(j, i)) <= 26) {
                    count += ways[j];
                }
            }
            ways[i] = count;
        }
        return ways[nums.length()];
    }
}

发表于 2024-09-17 18:02:25 回复(0)

Java

୧⍢⃝୨

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        int n = nums.length();
        if (n <= 1) {
            return nums.charAt(0) - '0' > 0 ? 1 : 0;
        }
        int[] dp =  new int[n];
        dp[0] = nums.charAt(0) - '0' > 0 ? 1 : 0;
        dp[1] = nums.charAt(1) - '0' > 0 ? dp[0] * 1 : 0;
        int num = Integer.parseInt(nums.substring(0, 2));
        if (num > 0 && num <= 26) {
            dp[1] += 1;
        }

        for (int i = 2; i < n; i++) {
            int val1 = nums.charAt(i) - '0';
            dp[i] = val1 > 0 ? dp[i - 1] * 1 : 0;
            int val2 = Integer.parseInt(nums.substring(i - 1, i + 1));
            if (val2 >= 10 && val2 <= 26) {
                dp[i] += dp[i - 2] * 1;
            }
        }
        return dp[n - 1];
    }
}

发表于 2024-08-05 15:48:54 回复(0)

Java

ShineGany

动态规划解该题，发现有点小坑，开始我一直纠结110，110110这种不应该都是1吗，结果官方题解是2和4

结果发现，动态规划应该考虑3种情况：

前两个数是10和20：dp[i] = dp[i-2];
考虑可以组合译码，11~26：dp[i] = dp[i-1] + dp[i-2];;
其他情况只有一种方式，直接译码：dp[i] = dp[i-1];

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // write code here
        if(nums.equals("0")) return 0;
        if(nums.equals("10") || nums.equals("20")) return 1;

        for(int i = 1; i<nums.length(); i++)
            if(nums.charAt(i) == '0' && nums.charAt(i-1) != '1' && nums.charAt(i-1) != '2')
                return 0;

        int[] dp = new int[nums.length() + 1];
        Arrays.fill(dp, 1);

        for(int i=2; i<=nums.length(); i++){
            // 考虑10和20的情况
            if(nums.charAt(i-1) == '0' && (nums.charAt(i-2) == '1' || nums.charAt(i-2) == '2')){
                dp[i] = dp[i-2];
            }
            // 考虑组合译码的情况（非10和20）
            else if(nums.charAt(i-2) == '1' && nums.charAt(i-1) != '0' ||
             nums.charAt(i-2) == '2' && nums.charAt(i-1) > '0' && nums.charAt(i-1) < '7'){
                dp[i] = dp[i-1] + dp[i-2];
            }
            // 直接译码
            else{
                dp[i] = dp[i-1];
            }
        }
        return dp[nums.length()];
    }
}

发表于 2024-05-29 16:20:04 回复(0)

Java

VXTW

import java.util.*;


public class Solution {
    public int solve (String nums) {
        int[] dp = new int[nums.length() + 1];
        if (nums.equals("0")) return 0;
        //初始化dp
        dp[0] = 1;
        dp[1] = 1;
        //中间部分
        for (int i = 2; i < dp.length; i++) {
            String str = "" + nums.charAt(i - 2) + nums.charAt(i - 1);
            if (nums.charAt(i - 1) == '0' && (nums.charAt(i - 2) != '1' &&
                                              nums.charAt(i - 2) != '2')) {
                return 0;
            }
            if (str == "00") {
                return 0;
            }
            if (str.equals("10") || str.equals("20") || (nums.charAt(i - 2) == '2' &&
                    nums.charAt(i - 1) > '6') || nums.charAt(i - 2) > '2' ||
                    nums.charAt(i - 2) == '0') {
                dp[i] = dp[i - 1];
            } else {
                dp[i] = dp[i - 2] + dp[i - 1];
            }

        }
        return dp[dp.length - 1];
    }
}

编辑于 2024-01-16 21:12:56 回复(0)

Java

牛客2024007号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // write code here
        // dp[i]，分割点在i时返回可能的编码结果数
        // 假设分割点在i， dfs(i) = dfs(i - 2)[在i - 2和 i - 1合法时] + dfs(i - 1)
        //排除0
        if(nums.equals("0")) 
            return 0;
        int len = nums.length();
        System.out.print(len);
        int[] dp = new int[len + 1];
        dp[1] = 1;
        dp[0] = 1;
        for(int i = 2; i <= len; i++) {
            int left = 0;
            int right = 0;
            if(judge(nums.substring(i - 2, i))) left = dp[i - 2];
            if(nums.charAt(i - 1) != '0') right = dp[i - 1];
            dp[i] = left + right;
        }
        return dp[len];
    }

    private boolean judge(String s) {
        if(s.charAt(0) == '0') return false;
        return Integer.valueOf(s) <= 26? true : false; 
    }
}

编辑于 2024-01-08 18:21:34 回复(0)

Java

卧没K

public class Solution {
    public int solve (String nums) {
        if(nums.charAt(0) == '0') return 0;
        int matrix[] = new int[nums.length()];
        matrix[0] = 1;
        for(int i = 1; i < nums.length(); i++) {
            int value = i == 1 ? 1 : matrix[i-2];
            matrix[i] = (nums.charAt(i) == '0' ? 0 : matrix[i-1]) + ( Integer.parseInt(nums.substring(i-1, i+1)) >= 10 && Integer.parseInt(nums.substring(i-1, i+1)) < 27 ? value : 0);
            if(matrix[i] == 0) return 0;
        }
        return matrix[nums.length()-1];
    }
}

发表于 2023-10-03 16:13:39 回复(0)

Java

TKitE

Java遍历：

import java.util.*;
public class Solution {
    public int f(String nums,int i){
        // 最后一位为0的情况
        if((i == nums.length()-1)&&nums.charAt(i)=='0'){
            return 0;
        }
        else if(i >= nums.length()-1){ // 字符串遍历结束
            return 1;
        }
        if(nums.charAt(i) == '0'){
            return 0;
        }
        else if(nums.charAt(i) > '2' || (nums.charAt(i) == '2' && nums.charAt(i+1) > '6')){
            return f(nums,i+1);
        }
        else{
            return f(nums,i+1) + f(nums,i+2);
        }
    }
    public int solve (String nums) {
        return f(nums,0);
    }
}

发表于 2023-08-25 21:44:03 回复(0)

Java

阿阿阿阿K

import java.util.*;


public class Solution {
    /**
        本质是爬楼梯，你想想当前层有多少种到达可能。无非就是看看i-1和i-2这两条路径中，哪一条可行。
     */
    public int solve (String nums) {
        // write code here
        //dp多一位
        int[] dp = new int[nums.length()+1];
        dp[0] = 0;
        //处理不同的初始情况，首位为0，则到达位置1的可能为0种，否则为1；
        if(nums.charAt(0) == '0'){
            dp[1] = 0;
        }else{
            dp[1] = 1;
        }
        //下面类似爬楼梯数爬法，到达当前的可能性，无法就是i-1和i-2这两种情况，哪条路径走得通。
        for(int i = 2; i <= nums.length(); i++){
            int method1= 0;
            int method2= 0;
            //i-1这条路径
            if(nums.charAt(i-1) != '0'){
                method1 = dp[i-1];
            }
            //i-2这条路径
            if(nums.charAt(i-2)>'0' && nums.charAt(i-2)<='1' 
                || nums.charAt(i-2)>'1' && nums.charAt(i-2)<='2' && nums.charAt(i-1)<='6'){
                //由于dp[0]=0, 当测试用例为"10"时，其实method为1。
                method2 = dp[i-2] == 0 ? 1 : dp[i-2];
            }

            dp[i] = method1 + method2;            
        }
        return dp[nums.length()];
    }
}

发表于 2023-08-11 16:24:21 回复(0)

Java

做则必成的勇气和信心

public int solve (String nums) {
        // 1-9  只有一种译码    11-19、21-26  两种译码  (除去10、20)
        //dp[i]，前i个数的译码方法有多少种
        //两种译码：直接译码(dp[i]=dp[i-1])和组合译码(dp[i]=dp[i-2])  所以dp[i]=dp[i-1]+dp[i-2]
        //一种译码：直接译码(dp[i]=dp[i-1])  所以dp[i]=dp[i-1]
        //依次相加，dp[length]
        if(nums.equals("0")) return 0;
        if(nums=="10"||nums=="20") return 1;
        //当0前面，不是1不是2，无法译码，0种   不是10、不是20  则无法译码
        for(int i=1;i<nums.length();i++){
            if(nums.charAt(i)=='0'){
                if(nums.charAt(i-1)!='1'&&nums.charAt(i-1)!='2'){
                    return 0;
                }
            }
        }
        //
        int[] dp=new int[nums.length()+1];
        Arrays.fill(dp,1);//初始化为1，有1种译码方式
        for(int i=2;i<nums.length()+1;i++){
            //11-19 21-26
            if(((nums.charAt(i-2)=='1'&&nums.charAt(i-1)!='0')||(nums.charAt(i-2)=='2'&&nums.charAt(i-1)<'7'&& nums.charAt(i-1)>'0'))){
                dp[i]=dp[i-1]+dp[i-2];
            }else{
                dp[i]=dp[i-1];
            }
        }
        return dp[nums.length()];
 
    }

发表于 2023-07-23 11:32:30 回复(0)

Java

Zhima1234

public class Solution {
    public int solve (String nums) {
        // nums[0,i-1]可以翻译成dp[i]种字符串
        int[] dp = new int[nums.length()];
        dp[0] = nums.charAt(0) == '0' ? 0 : 1;
        for (int i = 1; i < dp.length; i++) {
            if (nums.charAt(i) != '0') {
                dp[i] = dp[i - 1];
            }
            if (isValid(nums.charAt(i - 1), nums.charAt(i))) {
                if (i - 2 >= 0) {
                    dp[i] += dp[i - 2];
                } else {
                    dp[i]++;
                }
            }
        }
        return dp[nums.length() - 1];
    }
    private boolean isValid(char c1, char c2) {
        if (c1 == '0' || c1 >= '3') {
            return false;
        }
        if (c1 == '1') {
            return c2 >= '0' && c2 <= '9';
        }
        return c2 >= '0' && c2 <= '6';
    }
}

发表于 2023-05-31 11:06:33 回复(0)

Java

拒绝pua的小蜗牛很想潜水

import java.util.*;

public class Solution {

/**

* 解码

* @param nums string字符串数字串

* @return int整型

public int solve (String nums) {

// write code here

//排除0

if (nums.equals("0"))

return 0;

//排除只有一种可能的10 和 20

if (nums == "10" || nums == "20")

return 1;

//当0的前面不是1或2时，无法译码，0种

int[] dp = new int[nums.length() + 1];

//int dp1 = 1;

//int dp2 = 1;

dp[0]=1;

dp[1]=1;

for (int i = 2; i <= nums.length(); i++) {

//int temp = 0;

if (nums.charAt(i-1) == '0')

if (nums.charAt(i - 2) != '1' && nums.charAt(i - 2) != '2')

return 0;

if ((nums.charAt(i - 2) == '1' && nums.charAt(i - 1) != '0') ||

(nums.charAt(i - 2) == '2' && nums.charAt(i - 1) > '0' &&

nums.charAt(i - 1) < '7')) {

dp[i] = dp[i - 1] + dp[i - 2];

} else {

dp[i] = dp[i - 1];

}

return dp[nums.length()];

}

发表于 2023-03-20 20:07:37 回复(0)

Java

小鳖

    public int solve (String nums) {
        int pre1 = 1, pre2 = 0;
        char[] cs = nums.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            int t = pre1, cont = i == 0 ? 0 : (cs[i - 1] - '0') * 10 + cs[i] - '0';
            if (cs[i] == '0') pre1 = 0;
            if (i != 0 && cont <= 26 && cont >= 10) pre1 += pre2;
            pre2 = t;
        }
        return pre1;
    }

发表于 2023-02-08 18:00:58 回复(1)

Java

wpcAlex

import java.util.*;


public class Solution {
    public int solve (String nums) {
        // write code here
        int n = nums.length();
        String s = " " + nums;
        char[] cs = s.toCharArray();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i < n + 1; i++) { 
            // a : 代表「当前位置」单独形成 item
            // b : 代表「当前位置」与「前一位置」共同形成 item
            int a = cs[i] - '0', b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');
            // 如果 a 属于有效值，那么 f[i] 可以由 f[i - 1] 转移过来
            if (1 <= a && a <= 9) f[i] = f[i - 1];
            // 如果 b 属于有效值，那么 f[i] 可以由 f[i - 2] 或者 f[i - 1] & f[i - 2] 转移过来
            if (10 <= b && b <= 26) f[i] += f[i - 2];
        }
        return f[n];
    }
}

发表于 2023-01-24 13:53:52 回复(2)

Java

一天十题日渐沉迷

public class Solution {
    public int solve (String nums) {
        int n = nums.length();

        if (nums.charAt(0) == '0') {
            return 0;
        }
        // （时间优化）剪枝，去除无法编码的含0字符串
        for (int i = 1; i < n; i++) {
            if (nums.charAt(i) == '0') {
                if (nums.charAt(i - 1) == '0' || nums.charAt(i - 1) > '2')
                    return 0;
            }
        }

        // （空间优化）三指针替代DP数组
        int ppre = 1;
        int pre = 1;
        int cur = 1;
        for (int i = 1; i < n; i++) {
            // 等于'0'，则说明这个0只能和前一个字符一起编码
            // 此处不需要考虑0和前一个字符能否编码，因为无法编码的情况已经提前排除
            if (nums.charAt(i) == '0') {
                cur = ppre;
            } 
            // 不等于'0'，要看和前一个字符能否一起编码
            // 能一起编码，则存在两种编码方式，cur=pre+ppre
            // 不能一起编码，则只有一种编码方式，cur=pre
            else {
                int temp = Integer.parseInt(nums.substring(i - 1, i + 1));
                if (temp >= 10 && temp <= 26) {
                    cur = pre + ppre;
                } else {
                    cur = pre;
                }
            }
            ppre = pre;
            pre = cur;
        }
        return cur;
    }
}

发表于 2022-12-12 23:57:09 回复(0)

Java

键盘都敲坏了.

使用两个变量 dp1，dp2 ：

dp1保存当前遍历字符索引 - 2的位置时共有多少种翻译组合

dp2保存当前遍历字符索引 - 1的位置时共有多少种翻译组合

这两个变量不断随着循环向右移动，最终循环结束，dp2 即为解

public class Solution {
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // 如果开头是0，则失败返回0
        if(nums.startsWith("0")) return 0;
        // 获取字符串长度
        int size = nums.length();

        // dp1保存 当前遍历的i索引减2 的字符翻译次数
        // dp2保存 当前遍历的i索引减1 的字符翻译次数
        int dp1 = 1, dp2 = 1;
        for (int i = 1; i <= nums.length(); i++) {
            int temp = 0;
            if(nums.charAt(i - 1) != '0') temp = dp2; // temp等于上一个字符的翻译次数


            if(i - 2 >= 0){
                int num = Integer.parseInt(nums.substring(i - 2, i));
                if(num > 9 && num < 27){ // 如果当前字符可以和上一个字符组合成功，那么temp再加上 i-2个字符的翻译次数
                    temp += dp1;
                }
            }
            // 翻译次数 随着循环不断向右移动
            dp1 = dp2;
            dp2 = temp;
        }
        // 最终dp2即为解
        return dp2;
    }

}

发表于 2022-11-23 12:41:29 回复(0)

提交观点

问题信息

动态规划

上传者：牛客332641号

难度：

59条回答 1315收藏 5452浏览

通过挑战的用户

查看代码

牛客79085...

2023-02-19 08:55:07
一条咸鱼智

2022-09-16 16:19:11
得不到的最美

2022-09-16 15:25:43
captain...

2022-09-16 14:17:11
牛客40380...

2022-09-16 13:37:18

把数字翻译成字符串

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题