Easy-to-understand Python Solution 52ms


  • 0

    summary:

    1. split the string with '0' into segments;
    2. apply dp to every segment.
    class Solution(object):
        def decode(self, s):
            if len(s) == 0:
                return 1
            table = [1]*len(s)
            for i in range(1, len(s)):
                table[i] = table[i-1]
                if 10 < int(s[i-1:i+1]) <= 26:
                    table[i] += table[i-2]
            return table[len(s)-1]
    
        def numDecodings(self, s):
            if len(s) == 0:
                return 0
            slist = s.split('0')
            if '' in slist and slist.index('') != len(slist)-1:
                return 0
            ans = 1
            for i in range(len(slist)-1):
                if ans == 0 or slist[i][-1] not in ['1', '2']:
                    return 0
                ans *= self.decode(slist[i][:-1])
            ans *= self.decode(slist[-1])
            return ans
    

Log in to reply
 

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