See all coding puzzles and patterns here.

Problem Definition

Given a number, return all the different letter combinations that can be made from that number using the number mapping on a numeric phone pad: 

-------------------
|  1  |  2  |  3  |
|     | abc | def |
-------------------
|  4  |  5  |  6  |
| ghi | jkl | mno |
-------------------
|  7  |  8  |  9  |
| prqs| tuv | wxyz|
-------------------

Assume that the input only contains the numbers 2-9.

Examples

Some test cases to verify our solution.

assert set(letter_combos("23")) == {"ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"}
assert set(letter_combos("43")) == {"gd", "ge", "gf", "hd", "he", "hf", "id", "ie", "if"}
assert set(letter_combos("")) == set()

BFS Solution

While this is a graph traversal problem where we need to construct all the possible nodes and then compute all traversals, but we don't need to construct a formal graph. We can solve the problem by just iterating over all the possible characters for each number in the input and construct our list as we go, resulting in a breadth-first traversal of the solution space. 

def letter_combs(digits: str) -> list[str]:
    if not digits:
        return []
    mappings = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "prqs", "8": "tuv", "9": "wxyz"
    }
    ans = [""]
    for d in digits:
        ans_len = len(ans)
        chars = mappings[d]
        for i in range(len(chars) - 1):
            for j in range(ans_len):
                ans.append(ans[j] + chars[i])
        for j in range(ans_len):
            ans[j] = ans[j] + chars[-1]
    return ans

BFS Solution Complexity

Let $n =$ len(digits).

Runtime complexity should be $O(n \cdot 4^n)$ since we are multiplying the existing set of answers by 3 or 4 every time.

Auxiliary space complexity should be $O(1)$, since the ans values are part of the returned value.

Divide & Conquer Solution

We can also implement a divide & conquer solution for the problem by constructing subsets for each half of a number and then joining those sets. 

def letter_combs_dnc(digits: str) -> list[str]:
    n = len(digits)
    if n == 0:
        return []
    mappings = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "prqs", "8": "tuv", "9": "wxyz"
    }
    def dnc(start: int, end: int) -> list[str]:
        if start > end:
            return []
        if start == end:
            return [c for c in mappings[digits[start]]]
        mid = (start + end) // 2
        left = dnc(start, mid)
        right = dnc(mid + 1, end)
        ans = []
        for l in left:
            for r in right:
                ans.append(l + r)
        return ans
    return dnc(0, n - 1)

BFS Solution Complexity

Let $n =$ len(digits).

We will have $2 \cdot n$ recursive calls to dnc. In the leaves, we'll be constructing a list of length 3 or 4. In each call, we'll be doing on the order of $4^n$ calls. So our overall runtime complexity should be $O(n \cdot 4^n)$.

Auxiliary space complexity should be $O(n \cdot 4^n)$ for the same reason.