Letter Combinations of a Phone Number
Problem Statement
You are given a string digits
made up of digits from 2
through 9
inclusive.
Each digit (not including 1) is mapped to a set of characters as shown below:
A digit could represent any one of the characters it maps to.
Return all possible letter combinations that digits
could represent. You may return the answer in any order.
Example 1:
Input: digits = "34"Output: ["dg","dh","di","eg","eh","ei","fg","fh","fi"]
Example 2:
Input: digits = ""Output: []
Constraints:
0 <= digits.length <= 4
2 <= digits[i] <= 9
You should aim for a solution with O(n \cdot 4^n)
time and O(n)
space, where n
is the length of the input string.
Recommended Time and Space Complexity
You should aim for a solution with O(n \cdot 4^n)
time and O(n)
space, where n
is the length of the input string.
Hint 1
We can use a hash map to pair all the digits with their corresponding letters. Think of this as a decision tree, where at each step, we have a digit, and we select one of multiple characters to proceed to the next digit in the given string digits
. Can you think of an algorithm to generate all combinations of strings?
Hint 2
We can use backtracking where we select a character and process it, then backtrack to process another character. We recursively iterate on the given string with index i
. At each step, we consider the letters from the hash map that correspond to the digit at the i-th
index. Can you think of the base condition to stop this recursive path?
Hint 3
We initialize an empty string that represents the choices of the characters throughout the current recursive path. When the index i
reaches the end of the string, we add the current string to the result list and return.
Solution
Backtracking
def letter_combinations(digits: str) -> List[str]: digit_to_char = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "qprs", "8": "tuv", "9": "wxyz", } res = []
def backtrack(i, cur_str): if len(cur_str) == len(digits): res.append(cur_str) return for char in digit_to_char[digits[i]]: backtrack(i + 1, cur_str + char)
if digits: backtrack(0, "")
return res
Time complexity: O(n \cdot 4^n)
Space complexity: O(n)