一条包含字母 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]
}