Simple AC Python Top-Down DP


  • 0
    M
    class Solution(object):
        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """
            if (s == ""):
                return 0
            return self.decodingHelper(s, {})
            
        def decodingHelper(self, s, memoDict):
            if len(s) == 0:
                return 1
                
            if s[0] == "0":
                return 0
                
            if not s in memoDict:
                numWays = 0
                if len(s) >= 2 and int(s[0:2]) <= 26:
                        numWays += self.decodingHelper(s[2:], memoDict)
                numWays += self.decodingHelper(s[1:], memoDict)
                memoDict[s] = numWays
                
            return memoDict[s]

  • 0

    Very similar to mine, what is your runtime?


Log in to reply
 

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