Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
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:
Input: “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Backtrack
Create a mapping for easy access of letters.
mapping = [”, ”, ‘abc’, ‘def’,’ghi’, ‘jkl’, ‘mno’, ‘pqrs’, ‘tuv’, ‘wxyz’]
So mapping[2] == ‘abc’.
Use recursion
In each level of recursion, we will add the letters associated with the first digit in digits, aka mapping[digits[0]], to the current_comb, which holds part of the letter combinations we try to find. Then we will recurse with digits[0] removed and a new combination. EG: for ’23’, the current_comb will start with [‘a’, ‘b’, ‘c’] then in level 1 of recursion, we will append ‘d’ to each element to form new letter combinations. Then we will do the same with ‘e’ and ‘f’. Then we recurse with new cur_comb = [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]. Then we hit the base case since the input digits is now empty.
Caution
Need to make current comb non empty at the beginning
We need a non-empty cur_comb to recurse since we need to append chars to each combination to acquire new combinations.
Run time
This recursion doesn’t branch. One recursion only calls another one. But in each level of the recursion, the size of cur_comb changes. In first level, assuming each number has 3 letters associated with it, we have 3 numbers, then it becomes 9 because we append the second group of 3 letters to each existing 3 numbers one by one. It is like taking the dot product.
So if we have n numbers, in the end we will have n recursion and the output will be size 3^n so it is an O(EXP) algorithm.
Improvement
It ranked really low in Leetcode’s runtime.
Avoiding slicing list
Create a new function definition that doesn’t slice list. Instead, it will use a cur_pos to indicate which digit we are working on and return when we reach the end of the digits.
def recur(digits, cur_pos, current_comb):
if cur_pos == len(digits) :
res.extend(current_comb)
return
cur_digit = int(digits[cur_pos])
recur(digits, cur_pos + 1, current_comb)
It did becomes faster
Code
res = []
mapping = ['', '', 'abc', 'def','ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
def recur(digits, current_comb):
if not digits:
res.extend(current_comb)
return
cur_digit = int(digits[0])
cur_letters = [char for char in mapping[cur_digit]]
temp_comb = []
for char in cur_letters:
for comb in current_comb:
temp_comb.append(comb + char)
current_comb = temp_comb
recur(digits[1:], current_comb)
if not digits:
return []
current_comb = )]]
recur(digits[1:],current_comb)
return res
Iterative
Doing a dot product
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
Need to use backtrack to construct a tree and store the result
"""
res = []
mapping = ['', '', 'abc', 'def','ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
if not digits:
return []
res = [char for char in mapping[int(digits[0])]]
for i in range(1, len(digits)):
new_res = []
cur_letters = mapping[int(digits[i])]
for c in cur_letters:
for comb in res:
new_res.append(comb + c)
res = new_res
return res
It is super slow. Presumably it is because the triple for loop and the new_res we created at every outer loop slow the code down.
Using append/extend is problematic since we need to resize the array every time.
Improvement
List comprehension
for i in range(1, len(digits)):
new_res = []
cur_letters = mapping[int(digits[i])]
for c in cur_letters:
new_res.extend([comb + c for comb in res])
res = new_res
We can also take away another layer of for loop.
for i in range(1, len(digits)):
cur_letters = mapping[int(digits[i])]
res = [comb + letter for comb in res for letter in cur_letters]