首页 > 试题广场 >

把数字翻译成字符串

[编程题]把数字翻译成字符串
  • 热度指数:147698 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

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

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

数据范围:字符串长度满足 0 < n \leq 90
进阶:空间复杂度 ,时间复杂度
示例1

输入

"12"

输出

2

说明

2种可能的译码结果(”ab” 或”l”)  
示例2

输入

"31717126241541717"

输出

192

说明

192种可能的译码结果  
dp + dfs

public class Solution {
    int res = 0;
    public int solve (String nums) {
        // write code here
        //dp
        int len = nums.length();
        if (len == 0 || nums.charAt(0) == '0') return 0;
        int[] dp = new int[len+1];
        dp[0] = 1;
        for (int i=1;i<=len;++i){
            char c = nums.charAt(i-1);
            if (c != '0'){
                dp[i] = dp[i-1];
            }
            if (i-2 >= 0){
                int val = Integer.valueOf(nums.substring(i-2, i));
                if (val >=10 && val <= 26){
                    dp[i] += dp[i-2];
                }
            }
        }
        return dp[len];
        /*dfs(nums,0);
        return res;*/
        
        // dfs
   /* private void dfs(String nums, int start) {
        if(start >= nums.length()) {
            res++;
            return;
        }
        if(Integer.valueOf(nums.substring(start, start+1)) != 0) 
            dfs(nums,start+1);
        if(start < nums.length()-1 && Integer.valueOf(nums.substring(start, start+2)) >= 10 && Integer.valueOf(nums.substring(start, start+2)) <= 26)
            dfs(nums,start+2);*/
        
    }
}


发表于 2021-06-21 11:33:53 回复(0)
    public int solve (String nums) {
        if(nums.length() == 0 || nums.equals("0")){
            return 0;
        }
        int a=1,b=1;
        for(int i=2;i<=nums.length();i++){
            if(nums.charAt(i-1) == '0'){
                b=0;
            }
            int sum=0;
            String tmp = nums.substring(i-2,i);
            if(tmp.compareTo("10")>=0 && tmp.compareTo("26")<=0){
                sum = a+b;
            }else{
                sum = b;
            }
            a = b;
            b = sum;
        }
        return b;
    }
发表于 2021-04-29 15:41:55 回复(1)
class Solution {
public:
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        vector<int> dp(nums.size() +1,0);
        dp[0] = 1;
        dp[1] = nums[0] != '0'?  1 : 0;
        
        for (int i = 2; i <= nums.size(); ++i)
        {
            dp[i] = (isZero(nums[i-1])? 0 : dp[i-1]) + (isOverThreshold(nums[i-2], nums[i-1])? dp[i-2] : 0);
        }
        return dp[nums.size()];    
  
    }
    
    bool isZero(char const& a) const
    {
        return a == '0';
    }
    
    bool isOverThreshold(char const& a, char const& b) const
    {
        return a == '1' || (a == '2' && b <= '6');
    }
};
发表于 2021-04-24 22:35:09 回复(0)
class Solution:
    def solve(self, nums: str):
        if nums[0] == '0':
            return 0
        a = 1
        b = 1
        for i in range(1, len(nums)):
            tmp = b if nums[i] != '0' else 0
            if 9 < int(nums[i-1:i+1]) <= 26:
                tmp += a
            a, b = b, tmp
        return b

发表于 2021-04-03 14:46:56 回复(0)
public class Solution {
    public int solve (String nums) {
                // write code here
        int len = nums.length();
        // 首字符为0,直接返回0
        if (len == 0 || nums.charAt(0) == '0') return 0;
        int[] dp = new int[len+1];
        // dp[i] = dp[i-1]+dp[i-2],在某些条件下
        dp[0] = 1;
        for (int i=1;i<=len;++i){
            char c = nums.charAt(i-1);
            // 当前位置字符单独编码
            if (c != '0'){
                dp[i] = dp[i-1];
            }
            
            // 当前位置字符与前一个字符组合编码
            if (i-2 >= 0){
                int val = Integer.valueOf(nums.substring(i-2, i));
                // 当前位置为0且与前一个字符不能组合,则直接返回0
                if (c == '0' && (val == 0 || val > 26)) return 0;
                // 与前一个位置字符能组合,加上dp[i-2]。前一个字符为0则不能组合
                if (nums.charAt(i-2) != '0' && val <= 26){
                    dp[i] += dp[i-2];
                }
            }
        }
        return dp[len];
    }
}

编辑于 2021-02-27 10:37:27 回复(0)
public class Solution {
 
    public int solve(String nums) {
        if (nums.isEmpty() || nums.charAt(0) == '0') {
            return 0;
        }
        if (nums.length() == 1) {
            return 1;
        }
        int[] dp = new int[nums.length()];
        dp[0] = 1;
        int x1 = getX(nums, 1);
        if (x1 == 10 || x1 == 20) {
            dp[1] = 1;
        } else if (x1 <= 26 ) {
            dp[1] = 2;
        } else {
            dp[1] = 1;
        }
        for (int n = 2; n < nums.length(); n++) {
            int x = getX(nums, n);
            if (x == 10 || x == 20) {
                dp[n] = dp[n - 2];
            } else if (x <= 26 && x > 10) {
                dp[n] = dp[n - 1] + dp[n - 2];
            } else if (x < 10 && x > 0) {
                dp[n] = dp[n - 1];
            } else if (x == 0) {
                return 0;
            } else {
                dp[n] = dp[n - 1];
            }
        } 
        return dp[dp.length - 1];
    


    }

    private int getX(String nums, int i) {
        return (nums.charAt(i - 1) - '0') * 10 + (nums.charAt(i) - '0');
    }

}


发表于 2021-01-16 15:01:40 回复(0)
dp

class Solution {
public:
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        // write code here
        string s=nums;
        int n=s.size();
        vector<int> dp(n+1, 0);
        bool flag=true;
        dp[1] = s[0]=='0'?0:1;
        for(int i=2; i<=n; i++) {
            if(s[i-1]=='0' && s[i-2]=='0') {
                flag = false;
                break;
            }
            if(s[i-1]=='0') dp[i] = i-2>0?dp[i-2]:1;
            else if(s[i-2]=='0') dp[i] = dp[i-1];
            else {
                dp[i] += dp[i-1];
                if(s[i-2]=='1' || (s[i-2]=='2' && s[i-1]<='6' && s[i-1]>='1')) dp[i] += i-2>0?dp[i-2]:1;
            }
        }
        return flag?dp[n]:0;
    }
};


发表于 2020-08-06 16:40:36 回复(1)
import java.util.*;


public class Solution {
    public int solve (String nums) {
      //dp[i]: 以第i个字符结尾的子串有几种译码结果
      int[] dp = new int[nums.length() + 1];
      dp[0] = 1;  
      dp[1] = nums.charAt(0) == '0' ? 0 : 1;  //第一个字符
      for(int i = 2; i<=nums.length(); i++){
        char pre = nums.charAt(i-2), cur = nums.charAt(i-1);
        //('1~2' + '0') || ('2' + '7~9') || ('3~9' + '1~9')
        dp[i] = dp[i-1];
        if(cur == '0'){
          //('3~9' + '0') || '00'
          if(cur == '0' && pre != '1' && pre != '2'){
            return 0;
          }
        }else{
          //('1' + '1~9') || ('2' + '1~6')
          if(pre == '2' && cur <= '6' || pre == '1'){
            dp[i] = dp[i-1] + dp[i-2];
          }
        }
      }
      return dp[nums.length()];
    }
}

发表于 2022-02-12 12:42:30 回复(0)
你说你改个力扣的题就改,考边界条件你倒是把题说清楚,弄得自己试错试半天,比如1102能不能分成11和02来解,100能不能算合法,全tm自己碰出来的,真想骂人这题做的。力扣没费多大劲想出来的这儿熬一晚上,垃圾牛客。
public class Solution {
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // 带条件的青蛙跳台阶
        // 如果n位数和n-1位的数字组合而成的2位数在10-26闭区间中,f(n)=f(n-1)+f(n-2);
        // 否则f(n)=f(n-1)
        // 注意,有几个题干没说清楚的点在此补充:
        // 0+个位数不能当个位数来使,比如1102只能拆成1/10/2不能拆成11/02
        // 不能出现孤立0在末位的情况,比如100不能当成10/0处理,但010可以当成0/10处理
        // 字符串“0”算作0种译法
        if(nums.length()==0 || "0".equals(nums)){
            return 0;
        }
        int a = 1;
        int b = 1;
        int sum = 1;
        for(int i=1;i<nums.length();i++){
            // 计算和前一个数组成2位数的值
            int value = getValue(nums.charAt(i-1),nums.charAt(i));
            // 很重要的一步操作
            if(nums.charAt(i) == '0')
                b = 0;
            // 带条件的青蛙跳台阶
            if(value>=10 && value <=26){
                sum = a + b;
            }
            else{
                sum = b;
            }
            a = b;
            b = sum;
        }
        return sum;
    }
    
    public int getValue(char a, char b){
        return Integer.parseInt(""+a+b);
    }
}


发表于 2022-01-18 22:11:34 回复(5)
你这0一改,mid变hard了
发表于 2022-01-29 23:58:37 回复(0)
这道题主要是对0的处理,比如00这种是非法的,而10呢,则只有一种编码。
用dp[i]表示s[0,...,i-1]时的编码次数,那么:
如果s[i-1] == '0',dp[i] = 0,否则dp[i] = dp[i-1];
接着再根据s[i-1]s[i-2]更新dp[i]:
如果s[i-1] == '1',dp[i] += dp[i-2]
如果s[i-1] == '2'
       > s[i] <= 6,dp[i] += dp[i-2]                        
class Solution {
public:
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        vector<int> dp(nums.size()+1);
        if(nums.empty() || nums == "0") return 0;
        dp[0] = 1;
        for(int i = 1; i <= nums.size(); i++) {
            dp[i] = nums[i-1] == '0' ? 0 : dp[i-1];
            if((i > 1) && ((nums[i-2] == '1') 
                  || (nums[i-2] == '2' && nums[i-1] <= '6'))) {
                  dp[i] += dp[i-2];
            }
        }
        return dp[nums.size()];
    }
};


编辑于 2021-04-16 21:54:39 回复(2)
牛客可真够***的。
2种可能的译码结果(”ab” 或”l”)

这个是L,不是1,看了10分钟题目原来发现是L

发表于 2021-09-25 16:49:12 回复(1)
我在想一个问题  如果 给的字符串是 "110" ,答案算出来是 2种,但是实际上应该只有 1+10 这【一种】组合才对呀
发表于 2020-11-22 17:07:34 回复(5)
class Solution {
public:
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        // write code here
        if (nums.empty() || nums == "0") return 0;
        int n = nums.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            dp[i] = (nums[i - 1] == '0') ? 0 :dp[i - 1];
            if (i > 1 && (nums[i - 2] == '1' || (nums[i - 2] == '2' && nums[i - 1] <= '6'))) {
                dp[i] += dp[i - 2];
            }
        }
        return dp.back();
    }
};
发表于 2020-10-19 16:35:39 回复(0)
牛客这个示例,很多时候给了等于没给
发表于 2023-04-22 21:39:45 回复(1)
面向测试用例编程,哈哈哈
发表于 2022-04-18 21:07:37 回复(0)
class Solution:
    def solve(self , nums: str) -> int:
        # write code here
        if not nums&nbs***bsp;nums== '0':
            return 0
        a = b = 1  # a f(i-2) b f(i-1)
        for i in range(1,len(nums)):
            tmp = nums[i-1:i+1]
            if tmp == '00':   # 如果有00连续则无法翻译 返回0
                return 0
            # 有0的如 10 20看成可翻译的一个数,而不是两个数的情况
            # c = a + b if '11' <= tmp <= '26' and '0' not in tmp else b 
            c = a + b if '11' <= tmp <= '26' and tmp != '20' else b 
            a, b = b, c
        return b
有条件的青蛙跳, 不仅是11 到 26 还要对0进行处理
发表于 2021-12-17 11:02:45 回复(2)
    public int solve (String nums) {
        if(nums.equals("")) return 0;
        int n=nums.length();
        int[]dp=new int[n+1];//dp[i]表示长度为0时译码数
        dp[0]=1;
        dp[1]=nums.charAt(0)=='0'?0:1;//一位数只要不是0就是一种译码
        for(int i=2;i<=n;i++){
            int preTwo=Integer.parseInt(nums.substring(i-2,i));//计算自己和前一位是否能组成译码,前i-2和(i-1,i)形成一种译码情况
            if(preTwo>=10&&preTwo<=26){
                dp[i]=dp[i-2];
            }
          //检查这一位能否单独译码(这时候的情况是前i-1个和i形成译码)
          if(nums.charAt(i-1)!='0') dp[i]+=dp[i-1];
        }
        return dp[n];
    }

发表于 2021-03-26 20:42:15 回复(2)
    public int solve (String nums) {
        // write code here
        int n = nums.length();
        int[] dp = new int[n + 1]; // 定义:以nums[i - 1]结尾的字符串的译码次数
        dp[0] = 1; // 初始为1(对于dp[2]有用)
        dp[1] = nums.charAt(0) == '0' ? 0 : 1;
        for(int i = 2; i <= n; i++) {
            // 两种译码情况,要么当前数字单独译码,要么与前一位数字结合译码
            // 情况1:单独译码(条件是当前数字不是0才行)
            if(nums.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            // 情况2:要么与前一位数字结合译码,条件是结合后的数字不超过26
            if(nums.charAt(i - 2) == '1' || (nums.charAt(i - 2) == '2' && nums.charAt(i - 1) <= '6')) {
                dp[i] += dp[i - 2];
            }
            
        }
        return dp[n];
    }

发表于 2022-05-15 14:11:06 回复(0)
    /**
     * 解码 这题目本质和矩形覆盖和上楼梯都是一样的 一次编一个一次编两个
     * dp[i] 表示前i个字符的编码方式
     * 因为0不能被编码所以会有很多特殊情况
     * 1.当遍历到0 但前一个字符 不是1或2 无法编译返回0
     * 2.当遍历到0 但前一个字符是1 或 2 dp[i] = dp[i-2]
     * 3.遍历到的不是0 但和前一个组成的二位数范围不在可解码范围内 dp[i] = dp[i-1]
     * 4 其他 dp[i] = dp[i-1] + dp[i-2]
     * 
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        int m = nums.length();
        // 因为最后要返回dp[m] 前m个字符的编码方式 m可以看出字符个数
        int[] dp = new int[m + 1];
        dp[1] = 1; dp[0] = 1;
        for(int i = 2; i <= m; i++){
            // 如果遇到一个0前面不是1或者不是2直接返回0无法编译
            if(nums.charAt( i -1 ) == '0' && (nums.charAt(i - 2) != '1' && nums.charAt(i - 2) != '2' )) return 0;
            // 如果是0 前面一个为1
            if(nums.charAt( i -1 ) == '0') dp[i] = dp[i - 2];
            else {
                if((Integer.valueOf(nums.substring(i -2, i)) <= 26 && Integer.valueOf(nums.substring(i -2, i)) > 10)){
                    dp[i] = dp[i - 1] + dp[i - 2];
                }else dp[i] = dp[i - 1];
            }
        }
        return dp[m];
    }

发表于 2022-05-03 18:16:21 回复(0)