Letter Combinations of a Phone Number

TIP103 Unit 8 Session 2 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Recursion, Backtracking, Strings

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What does each digit map to?

  • Each digit from 2-9 maps to a fixed group of letters, just like an old T9 phone keypad: 2→“abc”, 3→“def”, 4→“ghi”, 5→“jkl”, 6→“mno”, 7→“pqrs”, 8→“tuv”, 9→“wxyz”.

• Does the order of the returned combinations matter?

  • No. The problem states the answer may be returned in any order, so we only need to produce every possible combination exactly once.

• How many letters does each combination contain?

  • One letter per input digit, so every combination has length len(digits).

HAPPY CASE
Input: digits = "23"
Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
Explanation: Digit 2 contributes one of "abc" and digit 3 contributes one of "def", giving 3 * 3 = 9 two-letter combinations.

EDGE CASE
Input: digits = ""
Output: []
Explanation: With no digits there are no combinations to build, so we return an empty list.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Generating All Combinations, we can consider the following approaches:

• Backtracking: Build each combination one digit at a time, choosing a letter for the current digit, recursing on the remaining digits, then undoing the choice to try the next letter.
• Iterative Cartesian Product: Repeatedly cross the partial results so far with the letters of the next digit; the recursive backtracking approach explores the same product depth-first.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Map each digit to its letters, then use backtracking to build combinations one position at a time. At index i we try every letter of digits[i], appending it to the current path and recursing on index i + 1. When the path is as long as digits, we record it as a complete combination and backtrack to explore other letters.

1) If `digits` is empty, return an empty list.
2) Build a keypad map from each digit '2'-'9' to its string of letters.
3) Define a backtracking helper `backtrack(index, path)`:
   a) Base case: if `index` equals the length of `digits`, join `path` into a string, add it to the results, and return.
   b) For each letter mapped to `digits[index]`:
      i)   Append the letter to `path`.
      ii)  Recurse with `index + 1`.
      iii) Pop the letter off `path` to backtrack.
4) Call `backtrack(0, [])` and return the collected results.

⚠️ Common Mistakes

• Returning [""] instead of [] when digits is empty.
• Forgetting to remove the letter from the path after recursing, so later combinations carry stale letters.
• Hardcoding three letters per digit and mishandling 7 (“pqrs”) and 9 (“wxyz”), which map to four letters.
• Recording the partial path before it covers every digit, producing combinations that are too short.

4: I-mplement

Implement the code to solve the algorithm.

def letter_combinations(digits):
    if not digits:
        return []

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

    combinations = []

    def backtrack(index, path):
        # Base case: one letter has been chosen for every digit
        if index == len(digits):
            combinations.append(''.join(path))
            return
        # Try every letter mapped to the current digit
        for letter in keypad[digits[index]]:
            path.append(letter)            # Choose
            backtrack(index + 1, path)     # Explore
            path.pop()                     # Un-choose (backtrack)

    backtrack(0, [])
    return combinations

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

• Input: digits = “23”

  • backtrack(0, []) tries ‘a’ for digit 2, then backtrack(1, ['a']) tries ‘d’, ‘e’, ‘f’ for digit 3, recording “ad”, “ae”, “af”.
  • Backtracking pops ‘a’, tries ‘b’, and the same inner loop records “bd”, “be”, “bf”.
  • Finally ‘c’ yields “cd”, “ce”, “cf”.
  • Output: [‘ad’, ‘ae’, ‘af’, ‘bd’, ‘be’, ‘bf’, ‘cd’, ‘ce’, ‘cf’]

• Input: digits = “”

  • The empty check triggers before any recursion.
  • Output: []

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of digits in the input and K is the largest number of letters mapped to a single digit (K = 4, for digits 7 and 9).

• Time Complexity: O(K^N * N) because there are up to K^N combinations and joining each completed path costs O(N).
• Space Complexity: O(N) for the recursion stack and the current path, not counting the O(K^N * N) output list.