639. 解码方法 2 [hard]

https://leetcode-cn.com/problems/decode-ways-ii/

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

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

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

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

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

示例 1 :

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

示例 2 :

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

说明 :

输入的字符串长度范围是 [1, 105]。
输入的字符串只会包含字符 '*' 和数字'0' - '9'。

通过次数2,021 | 提交次数7,358

First Try

2020-06-24

已经有091简单版的基础，直接就写出来了，不过边界判断条件有点多，还是有一次提交失败。

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int

        使用动态规划方法
        - 0开头的话，需要考虑10还是20,否则整体为0
        - 遇到*号，单独考虑为9种可能，双数考虑需要考虑到1和2.前者为1则有9种可能，前者为2则有2种可能。

        挂掉的用例： "*1*1*0", 又多了一个需要考虑*号的情况
        最后测试通过了，但是这里面琐碎的判断条件实在太多了。
        """
        overflow =  10 ** 9 + 7
        if s[0] == "0":
            return 0
        cache = ["" for i in range(len(s)+1)]
        cache[0] = 1
        cache[1] = 1 if s[0] != "*" else 9  # 这个真是没想到，还得考虑"*"号的初始条件"

        for i in range(2, len(s)+1):  # 需要考虑i-2, 因此需要从2开始
            j = i - 1
            if s[j] == "0":
                if s[j-1] in ("1", "2"):
                    cache[i] = cache[i-2]
                elif s[j-1] == "*":
                    cache[i] = 2 * cache[i-2]
                else:
                    return 0
            elif s[j] == "*":
                if s[j-1] == "1":
                    cache[i] = (cache[i-1] * 9 + cache[i-2] * 9)  % overflow  # *仅能代表1到9，而非0到9
                elif s[j-1] == "2":
                    cache[i] = (cache[i-1] * 9 + cache[i-2] * 6) % overflow
                elif s[j-1] == "*":
                    cache[i] = (cache[i-1] * 9 + cache[i-2] * 15) % overflow
                else:
                    cache[i] = (cache[i-1] * 9) % overflow
            # s[j] != "*" or "0"
            elif s[j-1] == "1" or (s[j-1] == "2" and 1<= int(s[j]) <= 6):
                cache[i] = (cache[i-1] + cache[i-2]) % overflow
            elif s[j-1] == "2" and int(s[j]) > 6:
                cache[i] = cache[i-1]
            elif s[j-1] == "*":
                if 1 <= int(s[j]) <= 6:
                    cache[i] = cache[i-1] + 2 * cache[i-2]
                else:
                    cache[i] = cache[i-1] + cache[i-2]
            else:
                cache[i] = cache[i-1]
        # print(cache[-2], cache[-1])
        return cache[-1] % overflow

639. 解码方法 2 [hard]​

First Try​

639. 解码方法 2 [hard]

First Try