# 17. Letter Combinations of a Phone Number

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]
``````