📚 Letter Combinations of a Phone Number – Java Cheat Sheet

📌 What Is It?

The Letter Combinations of a Phone Number problem involves generating all possible letter combinations for a given string of digits (2-9) based on the mapping of a telephone keypad.

📞 Keypad Mapping

Digit	Letters
2	a, b, c
3	d, e, f
4	g, h, i
5	j, k, l
6	m, n, o
7	p, q, r, s
8	t, u, v
9	w, x, y, z

🧱 Pattern Template

Recursive Backtracking

class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.isEmpty()) return new ArrayList<>();

        String[] mapping = {
            "", "", "abc", "def", "ghi", "jkl",
            "mno", "pqrs", "tuv", "wxyz"
        };
        List<String> result = new ArrayList<>();
        backtrack(0, digits, new StringBuilder(), result, mapping);
        return result;
    }

    private void backtrack(int index, String digits, StringBuilder current, List<String> result, String[] mapping) {
        if (index == digits.length()) {
            result.add(current.toString());
            return;
        }

        String letters = mapping[digits.charAt(index) - '0'];
        for (char letter : letters.toCharArray()) {
            current.append(letter);
            backtrack(index + 1, digits, current, result, mapping);
            current.deleteCharAt(current.length() - 1); // Backtrack
        }
    }
}

📊 Time Complexity

Time Complexity: O(4^N), where N is the length of the input string. Each digit can map to up to 4 letters.
Space Complexity: O(N), for the recursion stack.

✅ Use Cases

Generating all possible letter combinations for a phone number.
Exploring all combinations of characters for a given input.

📘 Common LeetCode Problems

17. Letter Combinations of a Phone Number [Medium] Backtracking

🧪 Example

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

Explanation:
- Digit '2' maps to ['a', 'b', 'c'].
- Digit '3' maps to ['d', 'e', 'f'].
- Combine all possible pairs.

🎥 Animation

Watch the animation for this problem: Letter Combinations Animation

💡 Pro Tips

Use a mapping array to store the letters for each digit.
Handle edge cases like empty input or invalid digits (e.g., '1' or '0').
Use backtracking to explore all possible combinations efficiently.