# Python Solution using Dynamic Programming

• 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]
``````

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