To generate all combinations, use backtracking. For each digit, try each of its letters. Recurse to the next digit. When you've processed all digits, add the combination to the result.
def letterCombinations(digits):
if not digits:
return []
phone = {
'2': 'abc', '3': 'def', '4': 'ghi',
'5': 'jkl', '6': 'mno', '7': 'pqrs',
'8': 'tuv', '9': 'wxyz'
}
result = []
def backtrack(index, path):
if index == len(digits):
result.append(''.join(path))
return
for letter in phone[digits[index]]:
path.append(letter)
backtrack(index + 1, path)
path.pop()
backtrack(0, [])
return result