Description
Return all strings formed by choosing one keypad letter for each digit in a string containing 2 through 9. Empty input returns an empty list.
Solution
def letter_combinations(digits):
if not digits:
return []
letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
result = [""]
for digit in digits:
result = [prefix + ch for prefix in result for ch in letters[digit]]
return resultExamples
Example 1
- Input
["23"]- Output
["ad","ae","af","bd","be","bf","cd","ce","cf"]
Choose an a/b/c letter then a d/e/f letter.
Example 2
- Input
[""]- Output
[]
Empty input has no combinations.
Example 3
- Input
["7"]- Output
["p","q","r","s"]
7 maps to four letters.
Approach
Start with an empty prefix. For each digit, extend every existing prefix by each letter mapped to that digit. After all digits, every prefix is a complete combination.
Time & space
O(d 4^d) time and O(d 4^d) space for output and constructed prefixes, where d is the digit count.