把数字翻译成字符串

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

热度指数：189588 时间限制：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种可能的译码结果

算法知识视频讲解

JavaScript Node

我睡觉的时候不困-

/**
 * 解码
 * @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
};

发表于 2021-11-21 18:45:46 回复(0)