Leetcode - 17. Letter Combinations of a Phone Number

Ever wondered how your phone predicts words when you’re typing on a numeric keypad? That’s exactly what this problem is about.

Back in the Nokia keypad era, if you pressed 2, it could mean a, b, or c. So typing 23 would give combinations like ad, ae, af, bd, … and so on.

That’s the real-world case we’re solving here — mapping digits to possible letter combinations.

---

📝 Problem Statement

Given a string containing digits from 2-9, return all possible letter combinations that the digits could represent.

Example:

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

---

💡 Approach

The problem is essentially about combinatorics and backtracking.

• Each digit maps to multiple characters (like 2 → abc).
• We need to explore all paths of combinations digit by digit.
• This screams backtracking — we build partial combinations, and when we reach the full length, we record the result.

Think of it like choosing clothes:

• Digit 2: Choose from a, b, c.
• Digit 3: Choose from d, e, f.
• Result = All possible outfits (ad, ae, af, ...).

---

⚡ Code

Here’s the complete implementation in JavaScript:

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
    let res = [];
    let numberToCharacterMap = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz"
    };

    const backtrack = (index, str) => {
        // Base case: if length matches digits, store result
        if (str.length === digits.length) {
            res.push(str);
            return;
        }

        // Explore each possible character
        for (let c of numberToCharacterMap[digits[index]]) {
            backtrack(index + 1, str + c);
        }
    };

    if (digits.length > 0) {
        backtrack(0, "");
    }
    return res;
};

---

⏱ Complexity Analysis

• Time Complexity:
  Each digit has at most 4 possible letters (7 and 9 have 4, rest have 3).
  For n digits → up to 4^n combinations.
  👉 O(4^n)

• Space Complexity:

  • Recursion depth = n.
  • Result storage = number of combinations (O(4^n)). 👉 O(n + 4^n)

---

🔑 Takeaway

This problem is a classic backtracking pattern. It shows up in many real-world cases like:

• Text prediction (phone keypads, T9 typing).
• Password/OTP generation.
• Combinatorial search in AI systems.

Next time you’re typing on a numeric keypad and your phone suggests words, you’ll know there’s a backtracking tree behind the scenes 😃.

---