Simple DP solution in Python with explanation comments


  • 2
    L
    class Solution(object):
    
        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """
            # if s begin with 0, return 0.
            if not len(s) or s[0] == '0':
                return 0
    
            total = 1
            pre = 1
    
            for i in range(1, len(s)):
    
                # when 0 appear, revert total to pre.
                if s[i] == '0':
                    if not s[i-1] in '12':
                        return 0
                    total = pre
                    continue
    
                # if 2-digits num can be decoded, add pre to total,
                # and save the previous total to pre.
                elif int(s[i-1:i+1]) < 27 and s[i-1] != '0':
                    pre, total = total, total+pre
    
                # all-is-well! forward to next step.
                else:
                    pre = total
    
            return total

  • 0
    B

    is "continue" necessary? You have if elif else, if the first "if" condition is satisfied, the latter ones won't execute anyways.


  • 0
    S

    very smart idea of pre, total = total, total+pre
    tho continue could be removed


Log in to reply
 

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