91. Decode Ways - LeetCode

class SolutionR1:  # O(n*n) / O(n) ? str slice
    def numDecodings(self, s: str) -> int:
        m = {'': 1}

        def recur(s=s):
            if s in m:
                return m[s]
            m[s] = 0
            if s[0] != '0':
                m[s] += recur(s[1:])
            if 10 <= int(s[:2]) <= 26:
                m[s] += recur(s[2:])
            return m[s]

        return recur()


class SolutionR2:  # O(n) / O(n)
    def numDecodings(self, s: str) -> int:
        m = {len(s): 1}

        def recur(i=0):
            if i in m:
                return m[i]
            m[i] = 0
            if s[i] != '0':
                m[i] += recur(i + 1)
            if 10 <= int(s[i : i + 2]) <= 26:
                m[i] += recur(i + 2)
            return m[i]

        return recur()


class Solution1:  # O(n) / O(n)
    def numDecodings(self, s: str) -> int:
        dp = [0] * (len(s) + 1)
        dp[0], dp[1] = 1, int(s[0] != '0')
        for i in range(len(s) - 1):
            if s[i + 1] != '0':
                dp[i + 2] += dp[i + 1]
            if 10 <= int(s[i : i + 2]) <= 26:
                dp[i + 2] += dp[i]
        return dp[-1]


class Solution2:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b = 1, int(s[0] != '0')
        for i in range(len(s) - 1):
            c = 0
            if s[i + 1] != '0':
                c += b
            if 10 <= int(s[i : i + 2]) <= 26:
                c += a
            a, b = b, c
        return b


class Solution3:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b = 1, int(s[0] != '0')
        for i in range(len(s) - 1):
            one, two = s[i + 1] != '0', 10 <= int(s[i : i + 2]) <= 26
            a, b = b, b * one + a * two
        return b


class Solution4:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b, p = 0, int(bool(s)), ''
        for c in s:
            tmp = b
            if c == '0':
                b = 0
            if 10 <= int(p + c) <= 26:
                b += a
            a, p = tmp, c
        return b


class Solution:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b, p = 0, int(bool(s)), ''
        for c in s:
            one, two = c != '0', 10 <= int(p + c) <= 26
            a, b, p = b, b * one + a * two, c
        return b