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': 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
Simple DP solution in Python with explanation comments
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.