Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent (like a phone keypad mapping). Return the answer in any order.

Example 1

Input: digits = "23" → Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2

Input: digits = "" → Output: []

Solution Approach

Map each digit to its corresponding letters. Use backtracking: at each position, try each letter for the current digit, then recurse to the next digit.

Create a digit-to-letters mapping (e.g., "2" → "abc").
If digits is empty, return empty list.
Use backtracking: at depth d, append each letter for digits[d] to the current path.
When path length equals digits length, add path to result and return.

Java

import java.util.*;

class Solution {
    private static final String[] MAP = {
        "", "", "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 d, StringBuilder path, List<String> result) {
        if (d == digits.length()) {
            result.add(path.toString());
            return;
        }
        for (char c : MAP[digits.charAt(d) - '0'].toCharArray()) {
            path.append(c);
            backtrack(digits, d + 1, path, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

Time Complexity: O(4^N * N). At most 4 letters per digit
Space Complexity: O(N) recursion depth