一条包含字母 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：
1
2
3
| 输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
|
示例 2：
1
2
3
| 输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
|
示例 3：
1
2
3
4
5
| 输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
|
示例 4：
1
2
3
| 输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。
|
提示：
1 <= s.length <= 100s 只包含数字，并且可能包含前导零。
对于字符串s = “226”，我们从左至右分析，字符 ‘ 2 ’ 可以解码为‘B’，字符 ’22‘ 可以解码为 ‘V’，解码方法总数为剩下的 ”26“ 和 ”6“解码方法总和，我们可以轻松知道 ”26“的解码方法为 2 种，”6“ 的解码方法为 1 种。
因此我们可以使用递归来实现这种思想
方法一：递归（超时）
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
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public int numDecodings(String s) {
if(s.length() == 0 || s.charAt(0) == '0'){
return 0;
}
char[] chars = s.toCharArray();
return decode(chars, 0);
}
private int decode(char[] chars, int start){
int n = chars.length;
if(start == n){
return 1;
}
if(chars[start] == '0'){
return 0;
}
int ret = decode(chars, start + 1);
if(start + 1 < n && isDigit(chars[start], chars[start + 1])){
ret += decode(chars, start + 2);
}
return ret;
}
private boolean isDigit(char upper, char lower){
int up = (int)(upper - '0');
int low = (int)(lower - '0');
if( (up == 1 && 0 <= low && low <= 9) || (up == 2 && 0 <= low && low <= 6)){
return true;
}
return false;
}
}
|
方法二：动态规划
虽然递归方法超时了，但我们可以尝试使用动态规划。dp[i] 表示 s[i … n] 的解码方法总数，结果为 dp[0]。我们可以使用 dpi, dpi1, dpi2 三个变量来代替 dp 数组，初始时 dpi = 0, dpi1 = 1, dpi2 = 1。我们可以列出如下 dp 方程：
$$
dp[i] = 0, s[i] = ‘0’
$$
$$
dp[i] = dp[i + 1], s[i] \neq ‘0’ & & \ !isDigit(s[i], s[i + 1])
$$
$$
dp[i] = dp[i + 1] + dp[i + 2], s[i] \neq ‘0’ & & \ isDigit(s[i], s[i + 1])
$$
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
| class Solution {
public int numDecodings(String s) {
int n = s.length();
if(n == 0 || s.charAt(0) == '0'){
return 0;
}
int dpi = 0, dpi1 = 1, dpi2 = 1;
for(int i = n - 1; i >= 0; i--){
if(s.charAt(i) != '0'){
dpi += dpi1;
if(i + 1 < n && isDigit(s.charAt(i), s.charAt(i + 1))) dpi += dpi2;
}
dpi2 = dpi1;
dpi1 = dpi;
dpi = 0;
}
return dpi1;
}
private boolean isDigit(char upper, char lower){
int up = (int)(upper - '0');
int low = (int)(lower - '0');
if( (up == 1 && 0 <= low && low <= 9) || (up == 2 && 0 <= low && low <= 6)){
return true;
}
return false;
}
}
|