Letter Combinations of a Phone Number

Problem

Autocomplete systems on phones map digit sequences to candidate words by enumerating all letter combinations the digits could spell. Given a string of digits (2-9), return all possible letter combinations they could represent using the standard telephone keypad mapping. Return an empty list for empty input.

Example 1:

Input: "57"
Output: ["jp","jq","jr","js","kp","kq","kr","ks","lp","lq","lr","ls"]

Example 2:

Input: ""
Output: []
Explanation: no digits means no combinations to generate.

Example 3:

Input: "7"
Output: ["p","q","r","s"]

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

Solution Breakdown

Approach: Backtracking where each recursion depth resolves exactly one digit.

Unlike subset or permutation generation, the loop here is not over an index range - it is over the letters mapped to the current digit. The recursion carries a single index into digits; at depth d the loop iterates phone_map[digits[index]], the letters for that one digit. For each letter it does choose-explore-unchoose: path.append(char), recurse with index + 1 to resolve the next digit, then path.pop(). The base case fires when index == len(digits) - the path now holds one character per digit, so "".join(path) is a complete combination and gets recorded. The tree's depth equals the number of digits, and each node fans out by the size of its digit's letter set (3 for most, 4 for 7 and 9). Trace "57": the root loops j, k, l for digit 5; under j it loops p, q, r, s for digit 7, emitting jp, jq, jr, js; backtracking to k and l yields the remaining eight - 12 strings total. The explicit empty-input guard if not digits: return [] is required, otherwise backtrack(0) would join an empty path and wrongly return [""].

Edge cases: Empty input returns [] (not [""]) thanks to the guard. A single digit produces one string per mapped letter.

Complexity: O(4^n * n) time, O(n) space - up to 4^n leaves (digits 7/9), each joined in O(n); recursion depth and path are bounded by the digit count n (output excluded).