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]