LeetCode Solution: 17. Letter Combinations of a Phone Number

Cracking the Code: Phone Number Letter Combinations (LeetCode 17) 🟡 Medium

Author Account: p1Hzd8mRM8
Publishing Time: 2026-05-31 22:35:29

---

Hey fellow coders! 👋 Have you ever wondered how old-school phone keypads could translate into a fun coding challenge? Today, we're diving into LeetCode problem 17: "Letter Combinations of a Phone Number." It's a fantastic problem to introduce you to the powerful concept of backtracking – a fundamental technique in competitive programming!

Don't worry if "backtracking" sounds intimidating. We'll break it down step-by-step, making it super clear and enjoyable. Let's get started! 🚀

---

2. Problem Explanation

Imagine an old-fashioned telephone keypad. Each digit (from 2 to 9) corresponds to a set of letters:

• 2 -> abc
• 3 -> def
• 4 -> ghi
• 5 -> jkl
• 6 -> mno
• 7 -> pqrs
• 8 -> tuv
• 9 -> wxyz

(Note: 1 doesn't map to any letters in this problem, just like on actual keypads for letters.)

The problem asks us to take a string of digits (e.g., "23") and return all possible letter combinations that these digits could represent.

Example 1: digits = "23"

• 2 maps to a, b, c
• 3 maps to d, e, f

If we combine them, we get:
ad, ae, af
bd, be, bf
cd, ce, cf
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2: digits = "2"

• 2 maps to a, b, c Output: ["a","b","c"]

Constraints:

• The input digits string will have a length between 1 and 4.
• Each character in digits will be a digit from '2' to '9'.

These constraints are quite friendly, meaning we don't have to worry about huge inputs, which is great for our chosen approach!

---

3. Intuition: Building Blocks and Choices

How do we even begin to generate all these combinations? Let's think about digits = "23":

1. We start with the first digit, '2'. What are our choices? a, b, or c.
2. Let's pick 'a'. Now, we move to the next digit, '3'. What are our choices for '3'? d, e, or f.
3. If we picked 'a' and then 'd', we get "ad". We've used all digits, so "ad" is a valid combination!
4. But what if after 'a', we picked 'e'? We get "ae".
5. And then 'f'? We get "af".

Notice a pattern? For each digit, we explore all its possible letters. This sounds a lot like building a tree of choices!

• Level 0 (Start): Empty string
• Level 1 (Digit '2'):
  • Choose 'a'
  • Choose 'b'
  • Choose 'c'
• Level 2 (Digit '3'):
  • If 'a' was chosen, then choose 'd', 'e', 'f'
  • If 'b' was chosen, then choose 'd', 'e', 'f'
  • If 'c' was chosen, then choose 'd', 'e', 'f'

This "explore all possibilities" and then "build up the result" is the core idea behind backtracking (or recursion).

---

4. Approach: The Backtracking Magic ✨

Backtracking is essentially a refined brute-force approach. You systematically try every possible path to find a solution. If a path doesn't lead to a solution (or leads to an invalid one), you "backtrack" (undo your last choice) and try another path.

For this problem, we'll use a recursive function:

1. Mapping: First, we need a way to quickly look up letters for each digit. A dictionary (or hash map) is perfect for this.
   

   digit_to_letters = {
       '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
       '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
   }
   

2. The Recursive Helper Function (backtrack):

   • It will take two main arguments:
     • idx: The index of the digit we are currently processing in the input digits string.
     • current_combination: The string built so far.
   • It also needs access to digits (the input string) and res (the list where we'll store our final combinations).

3. Base Case:

   • When do we know we've formed a complete combination? When idx (our current digit index) reaches the len(digits). This means we've processed all the digits.
   • At this point, we add our current_combination to our res list and return (stop this path of recursion).

4. Recursive Step:

   • Get the current_digit using digits[idx].
   • Look up its corresponding letters using our digit_to_letters map.
   • Now, iterate through each letter in these letters:
     • For each letter, we make a choice: append it to our current_combination.
     • Then, we make a recursive call to backtrack, moving to the next digit (idx + 1) and passing our updated combination (current_combination + letter).
   • Crucially, when the recursive call returns, because we are passing new strings (current_combination + letter), Python handles the "backtracking" part automatically. The current_combination in the current function call remains unchanged for the next iteration of the loop, allowing us to explore other choices from the current_digit.

Let's trace digits = "23" again with this logic:

backtrack(0, "")
idx = 0, current_combination = ""
current_digit = '2', letters = "abc"
* Loop for 'a':
backtrack(1, "a")
idx = 1, current_combination = "a"
current_digit = '3', letters = "def"
* Loop for 'd':
backtrack(2, "ad")
idx = 2, len(digits) = 2. idx == len(digits) is TRUE.
res.append("ad")
return
* Loop for 'e':
backtrack(2, "ae")
idx = 2. res.append("ae"). return
* Loop for 'f':
backtrack(2, "af"). res.append("af"). return
return (from backtrack(1, "a"))
* Loop for 'b':
backtrack(1, "b")
... (similar process for "bd", "be", "bf") ...
return
* Loop for 'c':
backtrack(1, "c")
... (similar process for "cd", "ce", "cf") ...
return
return res (from initial call)

This methodical exploration ensures we hit every single possible combination!

---

5. Code

Here's the Python implementation based on our backtracking approach:

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # Handle the edge case where the input is an empty string
        # Although constraints say 1 <= digits.length, it's good practice.
        if not digits:
            return []

        # Mapping of digits to letters
        digit_to_letters = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz',
        }

        # This list will store all the final combinations
        res = []

        # The backtracking recursive helper function
        # idx: current digit index we are processing
        # current_combination: the string built so far
        def backtrack(idx: int, current_combination: str):
            # Base case: If we have processed all digits
            # The length of our current_combination should be equal to the
            # total number of digits in the input.
            if idx == len(digits):
                res.append(current_combination)
                return

            # Get the current digit and its corresponding letters
            current_digit = digits[idx]
            letters = digit_to_letters[current_digit]

            # Iterate through each letter for the current digit
            for letter in letters:
                # Make a choice: append the letter to our combination
                # Then, recursively call backtrack for the next digit
                # with the updated combination.
                backtrack(idx + 1, current_combination + letter)

        # Start the backtracking process from the first digit (index 0)
        # with an empty initial combination string.
        backtrack(0, "")

        return res

---

6. Time & Space Complexity Analysis

Let N be the length of the input digits string.
Let M be the maximum number of letters a digit can map to (which is 4 for '7' and '9', and 3 for others).

Time Complexity: O(M^N * N)

• In the worst case, each digit can map to M (approximately 4) letters.
• Since we have N digits, and for each digit, we explore M choices, the total number of combinations generated will be roughly M^N.
  • For digits = "23", N=2, M=3 (avg). Combinations: 3 * 3 = 9.
  • For digits = "79", N=2, M=4. Combinations: 4 * 4 = 16.
• For each combination, we are building a string of length N. Appending characters to a string (or concatenating strings) in Python takes O(length_of_new_string) time. In our case, current_combination + letter creates a new string.
• Therefore, generating each of the M^N combinations takes O(N) time.
• Total time complexity: O(M^N * N).

Given N is very small (max 4), this M^N * N complexity is perfectly acceptable. For N=4 and M=4, 4^4 * 4 = 256 * 4 = 1024 operations, which is incredibly fast!

Space Complexity: O(M^N * N)

• Recursion Stack Space: The maximum depth of the recursion is N (one call for each digit). So, the space for the call stack is O(N).
• Result Storage: We store all the generated combinations in the res list.
  • There are M^N total combinations.
  • Each combination string has a length of N.
  • Therefore, the space required to store the results is O(M^N * N).

Combining these, the dominant factor is storing the results, so the overall space complexity is O(M^N * N).

---

7. Key Takeaways

1. Backtracking for Combinations: This problem is a classic example of when to use backtracking. Whenever you need to find all possible combinations or all possible paths by making a series of choices, backtracking is your go-to.
2. Recursive Structure: Backtracking problems are inherently recursive. Identify your:
   • Base Case: When do you stop recursing and record a result? (Here: when idx == len(digits)).
   • Recursive Step: How do you make a choice, recurse, and then potentially undo/try another choice? (Here: loop through letters, append, recurse).
3. State Management: Pay attention to how you pass and update your current_combination. In Python, string concatenation (+) creates new strings, which simplifies "undoing" (as the previous string state remains intact in the caller's scope).
4. Mapping: Using a dictionary (digit_to_letters) for quick lookups is efficient and clean.
5. Complexity: While backtracking can look exponential (M^N), it's often the nature of combinatoric problems. Always check constraints (N up to 4 here) to ensure your exponential solution is feasible.

---

8. Submission Details

• Author Account: p1Hzd8mRM8
• Publishing Time: 2026-05-31 22:35:29

This problem is an excellent stepping stone for understanding more complex backtracking problems like N-Queens, Sudoku Solver, or Permutations. Master this one, and you're well on your way! Keep coding and happy problem-solving! 🥳