Python Solution using Dynamic Programming


  • 0
    A

    Uses a recursion T(n) = combine(T[i:j-1] + T[j]) with base case as defined in the initialization of dict(memo)

    class Solution(object):
        def combine(self,fir,sec):
            if not fir and not sec:
                return []
            elif not fir and sec:
                return sec
            elif fir and not sec:
                return fir
    
            tmp = []
            for c in fir:
                for t in sec:
                    tmp.append(c+t)
            return tmp
            
        def letterCombinations(self, digits):
            """
            :type digits: str
            :rtype: List[str]
            """
            memo = {}
            memo[''] = []
            memo['0'] = [' ']
            memo['1'] = ['*']
            memo['2'] = ['a', 'b', 'c']
            memo['3'] = ['d', 'e', 'f']
            memo['4'] = ['g', 'h', 'i']
            memo['5'] = ['j', 'k', 'l']
            memo['6'] = ['m', 'n', 'o']
            memo['7'] = ['p', 'q', 'r', 's']
            memo['8'] = ['t', 'u', 'v']
            memo['9'] = ['w', 'x', 'y', 'z']
            
            if digits in memo:
                return memo[digits]
    
            memo[digits] = self.combine(self.letterCombinations(digits[:-1]),self.letterCombinations(digits[-1]))
            
            return memo[digits]
    

Log in to reply
 

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