Leetcode 17. Letter Combinations of a Phone Number

Let's understand what we're being asked to do. We have a string of digits like '23' and need to generate all possible letter combinations based on phone keypad mappings.

Tracing through '23': digit '2' maps to letters ['a','b','c'] and digit '3' maps to ['d','e','f']. We need all combinations: 'ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf' - that's 9 total combinations (3 × 3).

Important constraint: Each digit maps to 3-4 letters (digit '7' and '9' have 4 letters each). The input string length is at most 4, so we won't have an explosion of combinations.

Edge cases to consider: What if the input is empty? (return empty list). What if input has only one digit? (return all letters for that digit). The problem guarantees digits are only 2-9, so no need to handle '0' or '1'.

For each digit in the input, we need to choose one letter from its mapping. If we have 2 digits, we make 2 choices. If we have 3 digits, we make 3 choices.

This is a decision tree where at each level, we branch into multiple possibilities (one branch per letter option). Each path from root to leaf represents one valid combination.

By exploring all possible paths through this decision tree, we systematically generate every combination without missing any or creating duplicates.

The total number of combinations is the product of the number of letters for each digit. For '23': 3 letters × 3 letters = 9 combinations. For '234': 3 × 3 × 3 = 27 combinations.

Think of building a combination step-by-step, like filling in blanks: _ _ _ for input '234'.

For the first blank, try 'a' (from digit '2'), then recursively fill the remaining blanks. When you've filled all blanks, you have one complete combination. Then backtrack - undo the last choice and try the next option ('b', then 'c'). This explore-and-backtrack pattern naturally generates all combinations.

Use depth-first search with backtracking to explore all possible letter combinations. Start with an empty string and recursively add one letter at a time from each digit's mapping. When the current combination length equals the input digits length, we've found a complete combination - add it to results. Then backtrack by removing the last letter and trying the next option. This systematically explores the entire decision tree of letter choices.

def letter_combinations(digits):
    """
    Generate all possible letter combinations from phone keypad digits.
    Uses DFS/backtracking to explore all combinations.
    """
    if not digits:
        return []
    
    # Phone keypad mapping
    phone_map = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    
    result = []
    current = []
    
    def backtrack(index):
        # Base case: combination complete
        if index == len(digits):
            result.append(''.join(current))
            return
        
        # Get letters for current digit
        letters = phone_map[digits[index]]
        
        # Try each letter
        for letter in letters:
            # Choose: add letter to current combination
            current.append(letter)
            
            # Explore: recurse to next digit
            backtrack(index + 1)
            
            # Unchoose: backtrack by removing letter
            current.pop()
    
    # Start DFS from first digit
    backtrack(0)
    
    return result

• backtracking mastery: Understanding when and why to use backtracking data structure for this type of problem pattern
• Algorithm optimization: Recognizing how to achieve O(4^n × n) time complexity through efficient problem decomposition
• Implementation patterns: Learning the key coding techniques that make this solution robust and maintainable
• Problem-solving approach: Developing intuition for when to apply this algorithmic pattern to similar challenges
• Performance analysis: Understanding the time and space complexity trade-offs and why they matter in practice