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 · 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