Letter Combinations Phone LeetCode 17

LeetCode 17 gives you a string of digits from 2 to 9 and asks you to return all possible letter combinations that the number could represent on a phone keypad. For example, the input "23" maps digit 2 to "abc" and digit 3 to "def", producing nine combinations: ["ad","ae","af","bd","be","bf","cd","ce","cf"].

This is a classic backtracking problem. The solution space is a tree where each level corresponds to one digit in the input, and each branch at that level corresponds to one letter for that digit. Traversing all root-to-leaf paths in this tree gives all valid combinations.

The problem has a clean recursive structure: choose one letter for the current digit, recurse on the remaining digits, then backtrack and try the next letter. The base case is when all digits have been processed — at that point, the current combination is complete and added to the result.

The keypad mapping is fixed: digit 2 maps to "abc", 3 to "def", 4 to "ghi", 5 to "jkl", 6 to "mno", 7 to "pqrs", 8 to "tuv", and 9 to "wxyz". Store this as a Python dict or a Java HashMap/array indexed by digit character. This mapping is the only data structure needed beyond the recursion.

In Python, use a dict like phone = {"2": "abc", "3": "def", ...}. In Java, use a String array indexed 0-9 where phone[2] = "abc" etc., since digit characters can be converted to indices with ch - '0'. The array approach is slightly faster and avoids hash lookups.

Once you have the mapping, the rest of the algorithm is pure backtracking. At each recursive call, you look up the current digit in the map to get the candidate letters, then loop over each letter, append it to the current combination, recurse on the next digit, and remove the last letter before trying the next one.

The backtracking solution defines a recursive helper that takes the current digit index and the current combination string built so far. The base case is index == len(digits): when all digits have been consumed, add the current combination to the result list and return.

In the recursive case, look up digits[index] in the phone map to get its letters. For each letter, append it to the current combination, call the helper with index + 1, then remove the last character (backtrack). This pattern — choose, explore, unchoose — is the canonical backtracking template.

In Python, strings are immutable so you pass current + letter to each recursive call rather than mutating in place. In Java, use a StringBuilder and delete the last character after each recursive call for efficiency. Both approaches produce the same result; the StringBuilder version avoids creating many temporary string objects.

The iterative approach starts with a list containing one empty string: combinations = [""]. For each digit in the input, it expands every existing partial combination by appending each letter that corresponds to the current digit. After processing all digits, the list contains all complete combinations.

In Python this can be written concisely as a list comprehension: combinations = [combo + letter for combo in combinations for letter in phone[digit]]. Repeat this for each digit. The list grows from length 1 to the final product of letter counts per digit.

This approach processes combinations breadth-first — all one-character prefixes before two-character prefixes and so on. It produces the same output as backtracking and has the same time and space complexity, but avoids the call stack entirely.

The time complexity is O(3^m * 4^n) where m is the number of digits that map to 3 letters (digits 2, 3, 4, 5, 6, 8) and n is the number of digits that map to 4 letters (digits 7 and 9). Each combination requires O(L) time to construct where L is the length of the input, so the full time is O(L * 3^m * 4^n).

The space complexity is also O(3^m * 4^n) to store all combinations in the output list. The recursion stack adds O(L) depth at most, which is dominated by the output space. For the maximum input length of 4, the worst case is 4 digits all being 7 or 9, giving 4^4 = 256 combinations — entirely manageable.

In practice this problem always has small input (length 0-4), so the constants dominate and any correct implementation runs in effectively constant time. The complexity analysis matters more for understanding the scaling behavior in generalized versions of the problem.

The Python backtracking solution is typically 12-15 lines. Define the phone dict, initialize an empty results list, define the recursive helper with index and current string parameters, handle the base case by appending to results, then loop over phone[digits[index]] calling helper(index + 1, current + letter). The iterative Python version is even shorter: initialize combinations = [""] then for each digit use a list comprehension to expand.

The Java backtracking version uses a String array for the phone mapping indexed by digit value (phoneMap[2] = "abc" etc.), a List<String> for results, and a StringBuilder for the current combination. At each recursive call, append a character, recurse, then deleteCharAt(sb.length() - 1) to backtrack. Return results as a List<String>.

Both Python and Java solutions run in O(3^m * 4^n) time and space. The key implementation detail is handling the empty input: check if digits is empty or null at the start and return an empty list immediately — not a list containing an empty string.

Generate Parentheses (LeetCode 22) uses the same backtracking template: at each step choose to add an open or close parenthesis subject to validity constraints, recurse, then backtrack. Letter Combinations has no validity constraints — every letter choice is valid — making it one of the simpler backtracking problems and a good starting point.

Combination Sum (LeetCode 39) and Subsets II (LeetCode 90) extend the pattern to arrays with duplicate handling. The core structure — choose, recurse, unchoose — is identical; what changes is the candidate pool and the constraint that prevents invalid combinations or duplicates. Mastering Letter Combinations makes these problems straightforward extensions.

The backtracking family broadly includes permutations, combinations, subsets, word search, N-Queens, and Sudoku solver. They all share the same recursive DFS structure. Letter Combinations of a Phone Number is the cleanest example because the candidate pool (letters for a digit) is small, fixed, and has no pruning logic — making the pure backtracking pattern visible without distraction.