Domain 2MediumCORE

Letter Combinations of a Phone Number

We are given a string of digits (2-9). We need to map each digit to its corresponding letters on a standard telephone keypad (e.g., '2' -> 'abc', '3' -> 'def'). The goal is to generate every possible combination where the first letter comes from the set mapped by digits[0], the second from digits[1], and so on.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#String#Backtracking#Depth-first Search#Recursion

17. Letter Combinations of a Phone Number

Model: qwen3.5:9b
Topics: String,Backtracking,Depth-first Search,Recursion
FAANG asked: 1
Acceptance rate: 49.5%


Problem Breakdown

We are given a string of digits (2-9). We need to map each digit to its corresponding letters on a standard telephone keypad (e.g., ‘2’ -> “abc”, ‘3’ -> “def”). The goal is to generate every possible combination where the first letter comes from the set mapped by digits[0], the second from digits[1], and so on.

Inputs: A string of digits, length 0 to 4. Outputs: A list of strings representing all valid combinations. Order does not matter for correctness but typically sorted or lexicographical order is expected in practice (though problem says “any order”). Edge Cases:

  1. Empty Input (""): The output must be an empty list []. This often trips up recursive solutions if the base case isn’t checked before processing digits.
  2. Single Digit: Should return all letters for that digit, not combinations with nothing else (handled naturally by recursion depth).

Intuition

This is a combinatorial problem where we need to form strings based on choices at each step.

  1. Brute Force Attempt: One might think of generating permutations or using nested loops. However, the number of digits isn’t fixed; it’s dynamic (up to length 4). Writing four levels of nesting is impossible because NN varies.
  2. Key Insight: This structure suggests a tree traversal where each level represents processing one digit from the input string. At any node in this recursion tree, we have multiple branches corresponding to the letters for that specific digit.
  3. Algorithm Choice: Depth-First Search (DFS) via Backtracking is ideal here. We build the current combination character by character. Once we’ve used all digits provided in the input, we have a complete valid string and add it to our results list.

Approach

  1. Define a mapping dictionary for digits ‘2’ through ‘9’. Note that ‘0’, ‘1’, or non-digits are not expected per constraints but good practice is robustness (though here strictly adhering to constraints).
  2. Initialize an empty list result to store combinations.
  3. Create a recursive helper function, say backtrack(index, current_path):
    • Base Case: If index == len(digits), we have formed a complete string. Append current_path to result. Return.
    • Recursive Step: Retrieve the letters associated with digits[index]. Iterate through each letter:
      1. Add the letter to current_path.
      2. Call backtrack(index + 1, current_path).
  4. Handle the empty input case immediately before starting recursion to avoid unnecessary function calls or incorrect base cases (though checking inside handles it too).

Complexity Analysis

  • Time Complexity: O(4N⋅N)O(4^N \cdot N) where NN is digits.length.
    • There are at most 4 letters per digit. We generate a tree of depth NN. The number of leaf nodes (valid combinations) is roughly 3N3^{N} to 4N4^{N}.
    • For each valid combination, we perform string operations proportional to the length NN (to append or join). Thus, total time scales with output size.
  • Space Complexity: O(N+4N⋅N)O(N + 4^N \cdot N).
    • The recursion stack depth is O(N)O(N) for auxiliary space.
    • We must store all valid combinations in the result list, which takes proportional memory to the total number of characters generated (OutputSizeOutput Size). If we consider only auxiliary space excluding output storage, it is O(N)O(N).

Solution

class Solution:
    def letterCombinations(self, digits: str):
        # Handle empty input edge case immediately
        if not digits:
            return []
        
        # Mapping for phone keypad letters
        mapping = {
            '2': "abc", '3': "def", '4': "ghi", 
            '5': "jkl", '6': "mno", '7': "pqrs", 
            '8': "tuv", '9': "wxyz"
        }
        
        result = []
        
        def backtrack(index, current_path):
            # Base case: if we've processed all digits in the input string
            if index == len(digits):
                result.append(current_path)
                return
            
            # Get letters for the current digit at 'index'
            possible_letters = mapping[digits[index]]
            
            # Iterate through each letter to branch out our combinations
            for char in possible_letters:
                backtrack(index + 1, current_path + char)
        
        # Start recursion from index 0 with an empty path string
        backtrack(0, "")
        
        return result

Edge Cases Handled

  • Empty String (digits = ""): The function checks if not digits: return [] at the start. This prevents entering recursion and returning a list containing one empty string (which would be incorrect).
  • Single Digit: Recursion depth is 1, base case triggers immediately after first iteration loop completes for that digit’s letters. Returns correct single-letter strings in a list.
  • Max Length (digits.length = 4): The recursion handles dynamic length NN without fixed nesting levels. Time complexity remains bounded by the output size generated at this depth.