Simple DP solution in Python with explanation comments

  • 2
    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
                # 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.
                    pre = total
            return total

  • 0

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

  • 0

    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.