LeetCode 91 —— 91.解码方法
题目
91.解码方法
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'然而，在 解码 已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（“2” 和 “5” 与 “25”）。
例如，“11106” 可以映射为：
- “AAJF” ，将消息分组为 (1, 1, 10, 6)
- “KJF” ，将消息分组为 (11, 10, 6)
- 消息不能分组为 (1, 11, 06) ，因为 “06” 不是一个合法编码（只有 “6” 是合法的）。
- 注意，可能存在无法解码的字符串
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串，返回 0。
题目数据保证答案肯定是一个 32 位 的整数。
1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。
思路
从前往后遍历。
我们定义为 DP[i] 为字符串 s 的前 i 个字符 s[0…i] 的解码方法数。
我们以 121023 作为例子。
我们初始化 DP 和 s[0…i] 的关系：
i | 0 1 2 3 4 5
s[i] | 1 2 1 0 2 3
s[0..i] | 1 12 121 1210 12102 121023
DP[i] |
首先是 DP[0]，即 s[0] = 1，只有一种解码方法，所以 DP[0] = 1。
然后是 DP[1]，即 s[0..1] = 12。这一步，我们先用直觉来分析，有两种解码方法，即 1 2 和 12，所以 DP[1] = 2。
这个时候，我们更新一下表：
i | 0 1 2 3 4 5
s[i] | 1 2 1 0 2 3
s[0..i] | 1 12 121 1210 12102 121023
DP[i] | 1 2
接着是 DP[2]，即 s[0..2] = 121。
这一步，我们得稍微思考一下了。
最简单的，我们可以把最后一个 1 当做一个独立的字符来分析，这也是可行的，因为 1 就能够单独解码。
这样我们将前面的 12 看做一个整体，121 看成 12 和 1 的组合。
1作为独立个体时， 解码方法数就是前面的 12 的解码方法数，也就 = DP[1] = 2。
当然，我们也可以尝试把最后一个 1 和 它前面的 2 看做一个整体，21 也是能够解码的。这样的话，我们就可以把 121 看做是
1 和 21 的组合。
而 1 的解码方法数是 DP[0] = 1，所以这种情况下，21作为整体 的解码方法数是 DP[0] = 1。
将这两种方案加起来，就是 121 的解码方法总数。 DP[2] = 2 + 1 = 3。
我们再次更新这个表：
i | 0 1 2 3 4 5
s[i] | 1 2 1 0 2 3
s[0..i] | 1 12 121 1210 12102 121023
DP[i] | 1 2 3
接着是 DP[3]，即 s[0..3] = 1210。
经过上面的分析，我们大概能明白了，到了某一位的时候，解法就是“把这一位单独解码” 加上 “和前面一位组合起来” 的总结果。
但是在这里， 因为这一位是 0，所以我们需要特殊处理。
0 不能单独解码，所以这种方案是不可行的。
0 和 前面的 1 是一个组合，10 是可以解码的。这种情况下，1210 的解码方法数就是 12 的解码方法数，也就是 DP[1] = 2。
所以，综合起来， 1210 的解码方法数是 0 + DP[1] = 2。
我们再次更新表：
i | 0 1 2 3 4 5
s[i] | 1 2 1 0 2 3
s[0..i] | 1 12 121 1210 12102 121023
DP[i] | 1 2 3 2
接着是 DP[4]，即 s[0..4] = 12102。
这一位是 2，可以单独解码，所以 12102 的解码方法数就是 1210 的解码方法数，也就是 DP[3] = 2。
但是 02 是不可解码的。
所以 12102 的解码方法数就是 2 + 0 = 2。
依次类推就可以了。
当然，也有一些特殊情况，比如 100001：
我们可以先列出DP表：
i | 0 1 2 3 4 5
s[i] | 1 0 0 0 0 1
s[0..i] | 1 10 100 1000 10000 100001
DP[i] |
首先是 DP[0], 即 s[0] = 1，只有一种解码方法，所以 DP[0] = 1。
然后是 DP[1], 即 s[0..1] = 10，这一位是 0，不能单独解码，所以 DP[1] = 0。
接着是 DP[2], 即 s[0..2] = 100，
这个时候按照我们之前的思路，应该开始分情况讨论：
最后一位独立解码： 这一位是 0，不能单独解码，所以这种方案是不可行的。
与上一位组合解码： 这一位和上一位组合，得到的是00，这也是不可解码的。
也就是说，这个例子中，无论如何都是不可解码的。那么 DP[2] = 0。
并且这个时候，我们已经没有必要继续往下计算了，因为已经出现了无解的组合，再向下计算后面的字符也是没有意义的。
所以，这个时候，我们可以直接返回 0。
代码：
public class Q0091 {
@Test
public void test() {
System.out.println(numDecodings("226"));
}
@Test
public void test1() {
System.out.println(numDecodings("100001"));
}
@Test
public void test2() {
System.out.println(numDecodings("11106"));
}
@Test
public void test3() {
System.out.println(numDecodings("0"));
}
@Test
public void test4() {
System.out.println(numDecodings("12"));
}
/**
* 动态规划
*
* @param s
* @return
*/
public int numDecodings(String s) {
Set stringSet = new HashSet<>(Arrays.asList("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"));
int result[] = new int[s.length()];
if (s.length() == 1) {
if (stringSet.contains(s)) {
return 1;
} else {
return 0;
}
} else {
for (int i = 0; i < s.length(); i++) {
if (i == 0) {
if (stringSet.contains("" + s.charAt(i))) {
result[i] = 1;
} else {
return 0;
}
} else {
int tem = 0;
if (stringSet.contains("" + s.charAt(i))) {
tem += result[i - 1];
}
if (stringSet.contains("" + s.charAt(i - 1) + s.charAt(i))) {
if (i == 1) {
tem += 1;
} else {
tem += result[i - 2];
}
}
if (tem == 0) {
return 0;
}
result[i] = tem;
}
}
}
return result[s.length() - 1];
}
}
over~