Letter Combinations of a Phone Number

01 · Question

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 digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

02 · Analysis

One recursion level chooses a letter for the next input digit. Save a copy or joined string only after every digit has a choice; restore the path after each branch. For n digits there are at most 4^n outputs, so time and output space are O(n*4^n), with O(n) auxiliary path/stack space. Empty input returns an empty result for this problem, not a list containing an empty string.

03 · Solution

Reference solution

1def letterCombinations(digits: str) -> List[str]:
2    if not digits:
3        return []
4
5    phone_map = {
6        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
7        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
8    }
9    res = []
10
11    def dfs(i, cur_str):
12        if i == len(digits):
13            res.append(cur_str)
14            return
15
16        for char in phone_map[digits[i]]:
17            dfs(i + 1, cur_str + char)
18
19    dfs(0, "")
20    return res

Stepping Numbers

Combination Sum II