Python O(n) time O(1) space 48ms


  • 0
    E

    Key is to realize that at each position (i) you can generate combinations based on the integer value of the substring of s[i-1:i+1]. If this value is 0 (00) or is greater than 26 but the mod base 10 of it is 0, then we can't encode that value. If this value is <= 26 then we can add # of combinations generated by both the digit before and 2 digits before. If the value is > 26 then we can't generate additional combinations.

        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """
            if len(s) < 1 or s[0] == "0": return 0
            prev = cnt = 1
            for i in range(1, len(s)):
                b, t = int(s[i-1]), int(s[i])
                curr = b * 10 + t
                if curr == 0: return 0
                if t == 0: 
                    if curr > 26: return 0
                    cnt, prev = prev, cnt
                elif b == 0 or curr > 26: prev = cnt
                else: prev, cnt = cnt, prev + cnt
            return cnt
    

Log in to reply
 

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