Python DP solution with O(n) time complexity and O(1) space compexity


  • 0
    S
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return 0
        a = 1 if int(s[0]) >=1 and int(s[0])<=9 else 0
        if len(s) == 1:
            return a
        b = 1 if int(s[0:2])>=10 and int(s[0:2]) <= 26 else 0
        if a == 1 and int(s[1])>=1 and int(s[1])<=9:
            b += 1
        if len(s) == 2:
            return b
        for i in range(2,len(s)):
            c = 0
            single = int(s[i])
            double = int(s[i-1:i+1])
            if single>=1 and single<=9:
                c += b
            if double>= 10 and double<=26:
                c += a
            a = b
            b = c
        return c

Log in to reply
 

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