LeetCode 17. Letter Combinations of a Phone Number

🧩 Problem Description

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.

---

💬 Example

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

---

💡 Approach: Backtracking

This is a classic backtracking problem.
Each digit corresponds to a set of characters (phone keypad mapping).
We explore all possible combinations by building strings recursively.

🔢 Java Code

import java.util.*;

class Solution {
    private static final String[] KEYS = {
        "",    "",    "abc",  "def", "ghi", 
        "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

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

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

---

⏱ Complexity Analysis

• Time: O(4^n) → each digit can map to up to 4 letters
• Space: O(n) recursion depth

---

✍️ Summary

• Maps digits to characters based on phone keypad.
• Uses backtracking to explore all valid combinations.
• Very common interview question.

Related problems:

• lc-22 — Generate Parentheses
• lc-39 — Combination Sum
• lc-46 — Permutations
• lc-78 — Subsets