LEETCODE 639. Decode Ways II 解题思路分析

题目大意：

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

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

除了上述的条件以外，现在加密字符串可以包含字符 ‘*’了，字符’*’可以被当做1到9当中的任意一个数字。

给定一条包含数字和字符’*’的加密信息，请确定解码方法的总数。

同时，由于结果值可能会相当的大，所以你应当对10⁹ + 7取模。（翻译者标注：此处取模主要是为了防止溢出）

示例 1 :

输入: "*"
输出: 9
解释: 加密的信息可以被解密为: "A", "B", "C", "D", "E", "F", "G", "H", "I".

示例 2 :

输入: "1*"
输出: 9 + 9 = 18（翻译者标注：这里1*可以分解为1,* 或者当做1*来处理，所以结果是9+9=18）

说明 :

1. 输入的字符串长度范围是 [1, 10⁵]。
2. 输入的字符串只会包含字符 ‘*’ 和 数字’0′ – ‘9’。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=639

解题思路：

这道题在思路上并不算复杂，关键是一定要考虑全所有的情况。首先分析一下题目：

1. 数字1-26分别代表26个英文字母A-Z，其中需要注意这里的两位数字，比如26，它既可以代表字母Z，也可以代表字母BF，也就是说，你可以将26看做一个数，也可以看做2和6两个数，这是题目的核心。
2. 除了数字之外，本题还引入了一个通配符 ‘*’，这个星号可以代表1-9的任意一个数字，这就让题目的答案变得稍微复杂了一些。
3. 此外还要注意一些例外情况，所谓例外，就是无法通过给定的字符串解析出答案，比如字符串”00″,或者”0*”之类，简答来说，当出现字符’0’的时候，你就需要注意了。因为在1-26的数字中，只有10和20两个带零的数字，此外的应一律看做例外。

接下来说一下如何计算出解码方法的总数呢？核心的思想很简单，我们顺序循环字符串中每个字符，如果当前位置i对应字符能够与前一字符组成一个1-26之内的数字，那么截止到当前位置i为止能够解码的方法数应该为：count(i) + count(i-1)。我们举例来说明一下：

String s = "123";

比如当前位置i = 2，也就是数字3所在的位置，数字3可以和前一位数字2组成23这个合法数字，这样，我们可以将3看做是一个整体，也可以将23看做一个整体，所以字符串s可以理解为：

String s = "12[3]"; // count(i) = 2 ([1][2][3],[12][3])
String s = "1[23]"; // count(i - 1) = 1 ([1][23])

因此，当循环到数字3时， count(i ) + count(i – 1) 就是当前位置的解析方法数。

明白了基本原理，我们来分析一下有哪些情况可以合并数字？简单来说，只要2个字符组合到一起可以是26以下的数字就可以。但是需要注意一点，当后字符为0时，由于0不能单独存在，当前字符必须与后字符进行合并，因此与前字符就一定不能结合了。

一，当前字符为0，前字符为1或者2。这种情况下，因为0不能单独存在，必须与前字符进行合并，所以此时总count并不会因为出现合并而增加。即：
count = count(i – 1);

二，当前字符为0，前字符为*。与第一种情况相似，0必须与前字符*合并，不同的是，*可以代表任意数字，不过当前符合规则的只能是1和2，因此，0与*合并可能出现两种结果，10或者20，这时count(i)应为：
count = count(i – 1) * 2;

三，当前字符在1-9之间并且前字符为1，或者当前字符在1-6之间并且前字符为2。也就是说，组合后的数字是11-19或者21-26的情况，没有包含20的原因是因为第一种情况已经考虑过了。与前两种情况不同，当前字符可以单独存在，因此count(i)应为：
count = count(i – 1) + count(i);

四， 当前字符为*，并且后字符不为0。后字符为0归属于第二种情况。此时还要分为4种情况考虑，根据前字符的不同，与星号组合成的新字符的可能也不同。

如果前字符为1，那么可以组合成11-19的9种可能，另外星号单独存在时也存在9种方式，因此
count = count(i – 1) * 9 + count(i) * 9;

如果前字符为2，则有21-26的6种组合， 在考虑星号本身的9种情况：
count = count(i – 1) * 6 + count(i) * 9;

如果前字符也为*，那么两个星号可以组成的组合应为11-19以及21-26，共15种可能(注意星号的范围是1-9，不能代表0，所以没有10和20)
count = count(i – 1) * 15 + count(i) * 9;

除此之外，也就是前字符为3-9的情况，这时是无法与星号组成合法数字的，因此只考虑星号本身的9种可能即可。
count = count(i) * 9;

五，最后一种情况，当前字符不为*，前字符为*，并且后字符不为0。与第四种情况相似，同样不考虑后字符为0的情况，原因是在当前字符不为星号的前提下，如果是1或者2，那么将与第一种情况重复。如果当前字符大于3，那么将是例外。所有的例外情况我们会统一进行处理。因此忽略后字符为0的可能。此时，前字符为星号，当前为数字，这很像第三种情况，不过这里我们还是需要再进行2种分析，如果当前字符是在1和6之间，那么它与星号的组合会出现2中可能，比如11或者21，再比如16和26，此时
count = count(i – 1) * 2 + count(i);

如果当前数字在7到9之间，那么他们与星号的组合只可能出现一种可能
count = count(i – 1) + count(i);

到此，所有的可能出现组合的情况都已经分析完，最后还要考虑到例外情况，上文已经说过，凡是出现0的时候，我们就需要注意，0不能单独出现，它的前面必须有字符，并且前字符只能是1，0或者星号。除此之外的情况都属于例外，可以立即返回0。

最后看下完整代码：(注：其实此题的思路非常合适使用动态规划DP来解，但是为了分析清晰，随便写了一版通俗易懂的)

public int numDecodings3(String s) {
    int M = 1000000007;
    int length = s.length();
    long count_i = 1; // 当前位默认count为1
    long count_i_1 = 1; // 前一位默认count为1
    for (int i = 0; i < length; i++) {
        long count_i_1_temp = count_i_1;
        long count_i_temp = count_i;
        char c = s.charAt(i);
        char nextC = i < length - 1 ? s.charAt(i + 1) : '-';
        char preC = i > 0 ? s.charAt(i - 1) : '-';
        if (c == '0' && preC != '1' &&preC != '2' && preC != '*') {
            return 0;
        }
        count_i_1_temp = count_i;
        if (c == '0' && preC == '*') {
            count_i_temp = count_i_1 * 2 % M;
        }
        if ((c <= '6' && c >= '1' && preC == '2' || c <= '9' && c >= '1' && preC == '1') && (nextC != '0')) {
            count_i_temp = (count_i_1 + count_i) % M;
        }
        if (c == '*' && nextC != '0') {
            if (preC == '1') {
                count_i_temp = (count_i_1 * 9 + count_i * 9) % M;
            } else if (preC == '2') {
                count_i_temp = (count_i_1 * 6 + count_i * 9) % M;
            } else if (preC == '*') {
                count_i_temp = (count_i_1 * 15 + count_i * 9) % M;
            } else {
                count_i_temp = (count_i * 9) % M;
            }
        }
        if (c != '*' && preC == '*' && nextC != '0') {
            if (c <= '6' && c >= '1') {
                count_i_temp = (count_i_1 * 2 + count_i) % M;
            } else if (c <= '9' && c >= '7') {
                count_i_temp = (count_i_1 + count_i) % M;
            }
        }
        count_i_1 = count_i_1_temp;
        count_i = count_i_temp;
    }
    return (int) count_i;
}

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-639-decode-ways-ii-解题思路分析/