Problem Description
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = "" Output: []
Example 3:
Input: digits = "2" Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
The description was taken from https://leetcode.com/problems/letter-combinations-of-a-phone-number/.
Problem Solution
#O(3^N*4^M) Time, O(3^N*4^M) Space
#N is Numbers Mapped to 3 Digits
#M is Numbers Mapped to 4 Digits
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
mapping = {
'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'],
}
output = []
def backtrack(combo:list[str], start:int) -> None:
if len(combo) == len(digits):
output.append("".join(combo))
return
for letter in mapping[digits[start]]:
combo.append(letter)
backtrack(combo, start+1)
combo.pop()
backtrack([], 0)
return outputProblem Explanation
If we are given a problem that requires us to generate each possible combination of something, that is typically an indication that backtracking can be applied.
Backtracking is a Depth-First Search algorithm where we remove a choice whenever the DFS path yoyo returns to the given function. This allows us to circulate elements into each valid position so that we can generate each valid combination.
A general template for backtracking is to set a base case that appends a valid combination for a given DFS path to the output, check if a placement is valid, then make the placement. Once that placement is made, we'd go down a new DFS path with that placement and if that path didn't lead to a solution or it didn't lead to every solution like in this problem, we'd backtrack on the choice to make that placement by removing it from the combination.
This will allow us to circulate in each character for each digit position.
We will start by creating the mapping of the letters on the phone keys to its letter by implementing a HashMap. The description says that we are only going to have numbers between two and nine that we will be input. These mapping values can be seen in the reference picture from the description.
mapping = { '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'], }
Next, we will create our output array that will hold each possible combination string.
output = []
Let's create the base case for our recursive function.
If the length of the combo is zero, then that means we have reached the end of a DFS path so we have placed a valid combination that we can append to the output.
If that is the case, we will join the letters in the combination to form a string then append that string to the output and return from this DFS path.
if len(combo) == len(digits):
output.append("".join(combo))
return
Otherwise, we will look through the letters that are mapped to the digit of the starting index we were given in the recursive call, append a letter to the current DFS path combination, then continue down the DFS path of that combination.
combo.append(letter)
backtrack(combo, start+1)
Once the DFS yoyo returns here, we will pop the letter we just appended to the combo off so that we can circulate in the next letter.
combo.pop()
Here is what a few iterations of the process would look like with the input of "23".
One thing to note is the length of the recursive branch will be correlated to the length of the input string.
a
a
/
d pop
a
/
e pop
a
/
f pop
a pop
b
b
/
d pop
b
/
e pop
b
/
f pop
b pop
c
.
.
.
. c pop
Now that we have our backtrack function built, all we need to do is make the initial call by passing an empty combo and the first digit's starting index.
backtrack([], 0)
return output