Here is solutions for Letter Combinations of a Phone Number.

1. Understand the problem

• You are given a string of digits from 2–9. Each digit maps to a set of letters like on a classic phone keypad.

• Your task is to return all possible letter combinations that the digits could represe

• Example:

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

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. Can the input be empty?

• Yes. If digits == “”, return [].

1. Are digits guaranteed to be between 2–9?

• Yes (no 0 or 1 since they map to no letters).

1. What is the maximum length of digits?

• Usually ≤ 4 in LeetCode, but solution should generalize.

1. Do we need the result in any specific order?

• No strict order required, but typical DFS order is accepted.

1. Can the result be very large?

• Yes. Worst case is 4^n combinations.

• n is the number of character by the the number.

3. Explore examples.

1. Example 1:

Input: "23"
2 → [a,b,c]
3 → [d,e,f]

All combinations:
ad, ae, af
bd, be, bf
cd, ce, cf

1. Example 2:

Input: "79"
7 → pqrs (4 letters)
9 → wxyz (4 letters)

Total = 4 * 4 = 16 combinations

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1: Naive Recursive (Brute Force) - Time O(N * 4^N), Space O(N * 4^N), N is the length of character in each button

• Idea:

  • Try every letter for the first digit, then recursively build combinations for the rest.

• Time: O(N * 4^N)

• Space: O(N * 4^N)

4.2. Iteration - Time O(N * 4^N), Space O(N * 4^N)

• Idea: “23” => [””] → [“a”,”b”,”c”] → [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

5. Implement solutions.

Question time complexity: Why complexity is O(4^N * N) but not O(4^N) ?

• You don’t just count each combination — you also have to construct and copy a string of length N for every one of the 4ⁿ combinations.

• The extra * N comes from string construction cost.

5.1. Backtracking DFS - Time O(N * 4^N), Space O(N * 4^N), N is the length of character in each button

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        digitToChar = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "qprs",
            "8": "tuv",
            "9": "wxyz",
        }

        def backtrack(i, curStr):
            if len(curStr) == len(digits):
                res.append(curStr)
                return
            for c in digitToChar[digits[i]]:
                backtrack(i + 1, curStr + c)

        if digits:
            backtrack(0, "")

        return res

• Time: O(N * 4^N)

• Space: O(N * 4^N)

5.2. Iterative - Time O(N * 4^N), Space O(N * 4^N), N is the length of character in each button

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        res = [""]
        digitToChar = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "qprs",
            "8": "tuv",
            "9": "wxyz",
        }

        for digit in digits:
            tmp = []
            for curStr in res:
                for c in digitToChar[digit]:
                    tmp.append(curStr + c)
            res = tmp
        return res

• Time: O(N * 4^N)

• Space: O(N * 4^N)

6. Dry run testcases.

🔍 Dry Run: “23”

cur = ""
Try:
"a" → backtrack(1, "a")
"b" → backtrack(1, "b")
"c" → backtrack(1, "c")

• Branch “a”:

"a" + "d" → backtrack(2, "ad") → save
"a" + "e" → backtrack(2, "ae") → save
"a" + "f" → backtrack(2, "af") → save

• Branch “b”:

bd, be, bf

• Branch “c”

cd, ce, cf
```