把数字翻译成字符串

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()];
    }
}

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

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

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();
    }
};

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

    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];
    }

class Solution:
    def solve(self , nums: str) -> int:
        # write code here
        n = len(nums)
        dp = [0] * (n+1)
        dp[0] = 1
        dp[1] = 1 if nums[0] != '0' else 0
        print(dp)
        for i in range(2, n+1):
            if nums[i-1] != '0':
                dp[i] += dp[i-1]
            if '10'<= nums[i-2:i] <= '26':
                dp[i] += dp[i-2]
        return dp[n]

    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];
    }

    /**
     * 解码 这题目本质和矩形覆盖和上楼梯都是一样的 一次编一个一次编两个
     * 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];
    }

/**
 * 解码
 * @param nums string字符串 数字串
 * @return int整型
 */
function solve(nums) {
  let dp = new Array(nums.length + 1);
  dp[0] = 1;

  for (let i = 1; i <= nums.length; 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.length];
}
module.exports = {
  solve: solve
};