Skip to main content

解码方法

Tips

题目类型: Dynamic Programming

题目​

一条包含字母 A-Z 的消息通过以下映射进行了编码:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要解码已编码的消息, 所有数字必须基于上述映射的方法, 反向映射回字母(可能有多种方法). 例如, "11106" 可以映射为:

  • "AAJF", 将消息分组为 (1 1 10 6)
  • "KJF", 将消息分组为 (11 10 6)

注意, 消息不能分组为 (1 11 06), 因为 "06" 不能映射为 "F", 这是由于 "6" 和 "06" 在映射中并不等价.

给你一个只含数字的非空字符串 s, 请计算并返回解码方法的总数.

题目数据保证答案肯定是一个 32 位的整数.

提示:
  • 1 <= s.length <= 100
  • s 只包含数字, 并且可能包含前导零
示例
输入: s = "12"
输出: 2
解释: 它可以解码为 "AB"(1 2) 或者 "L"(12).
输入: s = "226"
输出: 3
解释: 它可以解码为 "BZ"(2 26), "VF"(22 6), 或者 "BBF"(2 2 6).
输入: s = "06"
输出: 0
解释: "06" 无法映射到 "F", 因为存在前导零("6" 和 "06" 并不等价).

题解​

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
  const n = s.length
  const dp = new Array(n + 1).fill(0)
  dp[0] = 1

  for (let i = 1; i <= n; i++) {
    if (s[i - 1] !== '0') {
      dp[i] += dp[i - 1]
    }

    if (
      i > 1 &&
      s[i - 2] !== '0' &&
      Number(s[i - 2]) * 10 + Number(s[i - 1]) <= 26
    ) {
      dp[i] += dp[i - 2]
    }
  }

  return dp[n]
}