Decode Ways II

Problem Id: 639 Difficulty: Hard


Intuition

1*6*321

1: 1 1*: S(1) * A(*) + A(1*) 1*6: S(1*) * A(6) + S(1) * A(6) 1*6: S(1*6) * A(*) + S(1*) * A(6*)

Solution


class Solution:
    def single(self, s):
        if "*" not in s:
            if s[0] == '0':
                return 0
            if 1 <= int(s) <= 26:
                return 1
        elif s == '*':
            return 9
        elif s == '**':
            return 15
        elif s[0] == '*':
            if 0 <= int(s[1]) <= 6:
                return 2
            else:
                return 1
        elif s[1] == '*':
            if int(s[0]) == 0:
                return 0
            elif int(s[0]) == 1:
                return 9
            elif int(s[0]) == 2:
                return 6
        return 0

    def numDecodings(self, s: str) -> int:
        mod = 10 ** 9 + 7
        if len(s) == 1:
            return self.single(s)
        p1 = self.single(s[0])
        p2 = self.single(s[:2]) + p1 * self.single(s[1])
        for i in range(2, len(s)):
            p1, p2 = p2, (p2 * self.single(s[i]) + p1 * self.single(s[i-1:i+1])) % mod
        return p2