17. Letter Combinations of a Phone Number

Hash Table
String
Backtracking
Recursion

TIME

O(4^n * n)

SPACE

O(n) recursion depth (excluding output)

Intuition

Every digit independently contributes one of its letters, so the full set of combinations is the Cartesian product of the per-digit letter groups. Backtracking builds each combination one digit at a time, branching over that digit's letters.

Approach

Map each digit 2..9 to its letter group.
Recurse over digit positions, carrying a partial string:
- At the end (all digits consumed), record the partial string.
- Otherwise, for each letter of the current digit, append it and recurse.
Return all collected strings. (An empty digits yields an empty list.)

Complexity

Time: O(4^n · n), up to 4^n combinations (digits 7 and 9 have 4 letters), each of length n to build
Space: O(n) recursion depth, plus the output

Edge Cases

Empty input → [] (not [""])
Single digit → that digit's letters (Example 2)
Digits 7 and 9 map to 4 letters, others to 3
Constraints cap length at 4, so at most 4^4 = 256 combinations

Code

from typing import List


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        """
        17. Letter Combinations of a Phone Number
        Time: O(4^n * n)
        Space: O(n) recursion depth (excluding output)
        """
        if not digits:
            return []

        mapping = {
            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
        }

        result = []

        def backtrack(idx: int, path: List[str]) -> None:
            if idx == len(digits):
                result.append("".join(path))
                return
            for ch in mapping[digits[idx]]:
                path.append(ch)
                backtrack(idx + 1, path)
                path.pop()

        backtrack(0, [])
        return result

import java.util.ArrayList;
import java.util.List;

/**
 * 17. Letter Combinations of a Phone Number
 * Time: O(4^n * n)
 * Space: O(n) recursion depth (excluding output)
 */
class Solution {
    private static final String[] MAPPING = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.isEmpty()) {
            return result;
        }
        backtrack(digits, 0, new StringBuilder(), result);
        return result;
    }

    private void backtrack(String digits, int idx, StringBuilder path, List<String> result) {
        if (idx == digits.length()) {
            result.add(path.toString());
            return;
        }
        String letters = MAPPING[digits.charAt(idx) - '0'];
        for (int i = 0; i < letters.length(); i++) {
            path.append(letters.charAt(i));
            backtrack(digits, idx + 1, path, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
}