Python Simple O(1) Space


  • 0

    O(1) space:

    class Solution(object):
        def numDecodings(self, s):
            if not s:
                return 0
            pre = 1
            ppre = 0
            for i in range(1, len(s) + 1):
                temp = pre
                if s[i - 1] == "0":
                    pre = 0
                if i > 1 and 10 <= int(s[i-2:i]) <= 26:
                    pre += ppre
                ppre = temp
            return pre
    

    O(n) space:

    class Solution(object):
        def numDecodings(self, s):
            if not s:
                return 0
            dp = [0] * (1 + len(s))
            dp[0] = 1
            for i in range(1, len(s) + 1):
                if s[i - 1] != "0":
                    dp[i] = dp[i - 1]
                if i > 1 and 10 <= int(s[i-2:i]) <= 26:
                    dp[i] += dp[i - 2]
            return dp[-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.