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

1
2
3
4
'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. 字符 0 必须跟在 1 或 2 后面
  2. 3 及以上的字符只能独立存在
  3. 1 之后可以接任意 1 个字符
  4. 2 之后可以接 0~5
  5. 动态规划，dp[n] = dp[n - 1]? or dp[n - 2]? or dp[n - 1] + dp[n - 2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var numDecodings = function (s) {
  if (s[0] === '0') {
    return 0
  }
  const dp = new Array(s.length + 1).fill(1)
  for (let i = 2; i <= s.length; ++i) {
    const v1 = Number(s[i - 2])
    const v2 = Number(s[i - 1])
    if (v2 === 0) {
      if (2 >= v1 && v1 >= 1) {
        dp[i] = dp[i - 2]
        continue
      } else {
        return 0
      }
    }
    if (v1 === 0) {
      dp[i] = dp[i - 1]
      continue
    }
    if (10 * v1 + v2 > 26) {
      dp[i] = dp[i - 1]
    } else {
      dp[i] = dp[i - 1] + dp[i - 2]
    }
  }
  return dp[s.length]
}