Python recursive and DP solution


  • 3
    G

    recursive - LTE even with cache - no go

    class Solution:
        # @param s, a string
        # @return an integer
        # 8:19
        def numDecodings(self, s):
            if s == '':
                return 1
    
            if s[0] == '0':
                return 0
    
            possibleDouble = True if self.isPossibleDouble(s[:2]) else False
    
            if possibleDouble:
                return self.numDecodings(s[1:]) + self.numDecodings(s[2:])
            else:
                return self.numDecodings(s[1:])
    
        def isPossibleDouble(self, num):
            return len(num) == 2 and (num[0] == '1' or (num[0] == '2' and num[1] <= '6'))
    

    DP

    class Solution:
        # @param s, a string
        # @return an integer
        def numDecodings(self, s):
            if not s:
                return 0
    
            n = len(s)
            dp = [0] * (n + 1)
            dp[0] = 1
            
            for i in range(1, n + 1):
                if s[i-1] != '0':
                    dp[i] += dp[i-1]
                if len(s[i-2:i]) == 2 and '10' <= s[i-2:i] <= '26':
                    dp[i] += dp[i-2]
    
            return dp[n]

  • 0
    C

    I had doubt about the recursive so I copy past it and it fails the test case without reaching an LTE. Either the tests have change or it do not works.


Log in to reply
 

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