Letter Combinations of a Phone Number

Difficulty: Medium | Acceptance: 64.38% | Paid: No

Topics: Hash Table, String, Backtracking

• Examples
• Constraints
• Brute Force - Recursive Backtracking
• Iterative with Queue
• Optimized Recursive Backtracking (String Building)

Examples

Example 1

Input:

digits = "23"

Output:

["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2

Input:

digits = "2"

Output:

["a","b","c"]

Constraints

- 0 <= digits.length <= 4
- digits[i] is a digit in the range ['2', '9']

Brute Force - Recursive Backtracking

Intuition

The problem asks for all possible combinations, which naturally suggests a recursive approach or backtracking. We can exhaustively explore all possible letter combinations by making choices at each digit and backtracking when reaching a dead end.

Steps

• Create a mapping of digits to their corresponding letters (as on a phone keypad).
• Use a recursive function to build combinations character by character.
• The base case occurs when the current combination’s length equals the input digits’ length. At this point, add the combination to the result list.
• For each digit in the input, iterate through its corresponding letters. For each letter, make a choice, recurse for the next digit, and then backtrack (remove the choice) to explore other possibilities.
• Handle the edge case of an empty input string by returning an empty list.

def letterCombinations(digits):
    if not digits:
        return []
    
    phone_map = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    
    def backtrack(index, path):
        if index == len(digits):
            combinations.append(''.join(path))
            return
        
        possible_letters = phone_map[digits[index]]
        for letter in possible_letters:
            path.append(letter)
            backtrack(index + 1, path)
            path.pop()
    
    combinations = []
    backtrack(0, [])
    return combinations

Complexity

• Time: O(3^N * 4^M) where N is the number of digits that map to 3 letters (2,3,4,5,6,8) and M is the number of digits that map to 4 letters (7,9). This is because for each digit, we might have 3 or 4 choices. The worst case is when all digits are 7 or 9. The 3^N * 4^M term accounts for all possible combinations, and we generate each combination exactly once.
• Space: O(3^N * 4^M) to store all the combinations in the output. The recursion depth can go up to N+M, which contributes to the call stack space, but this is typically dominated by the output space. For the recursion stack, it’s O(N+M).
• Notes: This is a classic backtracking algorithm. The time complexity is exponential because we’re generating all possible combinations. Each recursive call explores a possible letter from the current digit, and we make choices for each digit in sequence. The space complexity is primarily driven by the need to store all valid combinations. The auxiliary space for recursion is linear with respect to the input length.

Iterative with Queue

Intuition

Instead of recursion, we can use an iterative approach. We start with an empty string and iteratively build combinations by appending possible letters for each digit. A queue (or a list) can help manage the intermediate combinations.

Steps

• Handle the base case where the input digits string is empty.
• Initialize a queue (or list) with an empty string to start building combinations.
• Iterate through each digit in the input string.
• For each digit, get its corresponding letters.
• While the queue is not empty and the length of the front item equals the current digit index (before processing this digit), pop an item.
• For each possible letter of the current digit, append the letter to the popped item and add it back to the queue.
• After processing all digits, the queue contains all valid combinations.
• Convert the final queue to a list and return.

from collections import deque

def letterCombinations(digits):
    if not digits:
        return []
    
    phone_map = {
        '2': 'abc', '3': "def", '4': "ghi", '5': "jkl",
        '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz"
    }
    
    queue = deque([''])
    
    for digit in digits:
        letters = phone_map[digit]
        # Process all combinations of the current length
        for _ in range(len(queue)):
            combination = queue.popleft()
            for letter in letters:
                queue.append(combination + letter)
    
    return list(queue)

Complexity

• Time: O(3^N * 4^M) where N and M are as defined in the brute force approach. The time complexity is the same because we’re still generating all possible combinations. Each combination is built incrementally, and every valid combination is generated once.
• Space: O(3^N * 4^M) for the space required to store all combinations. The queue can also grow to hold a number of intermediate strings proportional to the final output size, but this is also bounded by the output size.
• Notes: This approach is iterative and avoids recursion. It’s essentially a breadth-first search on the implicit tree of combinations. The queue holds partial combinations, and for each digit, we process all current combinations in the queue. The space for the queue can peak at a significant fraction of the final output size, making it less efficient in terms of auxiliary space than the recursive approach. However, it avoids potential stack overflow issues with deep recursion. The time complexity is the same as the recursive approach since the same amount of work is performed.

Optimized Recursive Backtracking (String Building)

Intuition

The standard recursive backtracking approach can be slightly optimized by using string concatenation directly instead of a list for path tracking, simplifying the logic a bit at the cost of potentially more string operations.

Steps

• Set up the digit-letter mapping as before.
• Define a recursive helper function that takes the current index and the current combination string.
• If the current combination’s length equals the input digits’ length, add it to the result list.
• Otherwise, for the current digit, iterate through its letters, and for each letter, recursively call the function with the next index and the combination string appended with the current letter.
• This approach avoids explicit backtracking steps by using the call stack to manage the state of the combination string.
• Handle the empty input base case.

def letterCombinations(digits):
    if not digits:
        return []
    
    phone_map = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    
    def backtrack(index, current_combination):
        if index == len(digits):
            combinations.append(current_combination)
            return
        
        possible_letters = phone_map[digits[index]]
        for letter in possible_letters:
            backtrack(index + 1, current_combination + letter)
    
    combinations = []
    backtrack(0, "")
    return combinations

Complexity

• Time: O(3^N * 4^M) where N and M are as defined in the brute force approach. The time complexity is still exponential because we generate all possible combinations. Each string concatenation operation could take O(K) time where K is the length of the string, but this is typically considered a constant factor in this context.
• Space: O(3^N * 4^M) for storing the output combinations. The recursion stack contributes O(N+M) space. The difference from the first approach is that string concatenation might create temporary strings, but the overall space complexity in terms of the final output is the same.
• Notes: This optimized recursive approach simplifies the code by not explicitly managing a path list. String concatenation is used to build combinations, and the call stack naturally handles the backtracking of string state. While the string concatenation currentCombination + letter creates a new string object in languages with immutable strings (like Python, Java, JavaScript, C#), this is a common idiom in recursive string-building problems. The time and space complexities are equivalent to the standard recursive backtracking approach, but the constant factors might be slightly different due to string handling. This is often more readable but might be slightly less efficient for very long strings due to repeated string allocations.