class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
table = {
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']
}
ans = []
def backtrack(i, curr):
if len(curr) == len(digits):
ans.append(''.join(list(curr)))
return
else:
for val in table[digits[i]]:
curr.append(val)
backtrack(i+1, curr)
curr.pop()
backtrack(0, [])
return ans