Please review my solution and explanation


  • 0
    S
        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """
            def util(x):
                """
                    x - an input string of either one or two characters
                    returns a number of ways to represent a string x
                """
                if x.isdigit() == False:
                    return 0 # if string is non digit, we can't decode it
                else:
                    d = int(x)
                    if d == 0 or x[0] == '0':   # if digit is either 0 or x begins with '0' then cant decode it
                        return 0
                    if 1 <= d <= 26:
                        # strings '1','2'....'26'
                        return 1
                    else:
                        # anything above '26', can't decode it
                        return 0
            
            if s == None or len(s) == 0:
                return 0
                
            n    = len(s)
            func = [ 0 for i in range(n)]  # func[i] = number of ways to decode a string s[0:i+1] or s0s1s2....si character string
            
            func[0] = util(s[0])    # how many ways can you decode first character
            
            if n > 1: # if at least 2 chars are present
                func[1] = func[0]*util(s[1]) + util(s[0:2]) # how many ways can you decode first couple
            
            for i in range(2,n):
                # formula is based on observation that number of ways to decode 
                # numberOfWaysToDecode(s[0:i+1]) = numberOfWaysToDecode(s[0:i]) * numberOfWaysToDecode(s[i]) + numberOfWaysToDecode(s[0:i-2]) * numberOfWaysToDecode(s[i-1:i+1])
                # Why above formula?
                #   Assume we have a string (s0, s1, s2....si-1) and now we append si to it to form (s0,s1,s2...si-1,si)
                #       Then si can be on its own in which case partition decoding as (s0,s1,s2...si-1) | si --- first term of formula
                #       AND si can be with its preceeding char in which case partition decoding as (s0,s1,s2...si-2) | (si-1,si) --- second term of formula
                
                func[i] = func[i-1] * util(s[i]) + func[i-2] * util(s[i-1:i+1])
            
            return func[n-1] # number of ways to decode s[0:n]

Log in to reply
 

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