DFS with memorization in Python


  • 0
    E
    
    class Solution(object):
        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """
            def _dfs(s):
                if len(s)==0:
                    return 1
                if s[0]=='0':
                    return 0
    
                d1 = 0
                if s[1:] in mem:
                    d1 = mem[s[1:]]
                else:
                    d1 = _dfs(s[1:])
                    mem[s[1:]] = d1
    
                d2 = 0
                if len(s) > 1 and int(s[:2]) >= 1 and int(s[:2]) <= 26:
                    if s[2:] in mem:
                        d2 = mem[s[2:]]
                    else:                    
                        d2 = _dfs(s[2:])
                        mem[s[2:]] = d2
    
                return d1 + d2
    
            mem = {}
    
            if len(s)==0:
                return 0
    
            return _dfs(s)
    

Log in to reply
 

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