We can solve this problem using an iterative approach with queue-based BFS (Breadth-First Search). Here’s how we can implement it:

from typing import List
from collections import deque

def letter_combinations(digits: str) -> List[str]:
    if not digits:
        return []

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

    # Initialize a queue with an empty string
    queue = deque([""])

    # Perform BFS
    for digit in digits:
        # Get the letters corresponding to the current digit
        letters = digit_mapping[digit]
        # Determine the current queue size
        size = len(queue)
        # Add combinations of the current digit to the existing combinations
        for _ in range(size):
            current_combination = queue.popleft()
            for letter in letters:
                queue.append(current_combination + letter)

    return list(queue)

# Example usage:
print(letter_combinations("23"))  # Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
print(letter_combinations(""))    # Output: []
print(letter_combinations("2"))   # Output: ["a", "b", "c"]

Explanation:

  • We use a queue-based BFS approach to generate all possible combinations.
  • We initialize a queue with an empty string to start the process.
  • We iterate through each digit in the input digits string.
  • For each digit, we retrieve the corresponding letters from the digit_mapping dictionary.
  • We determine the current size of the queue to process all existing combinations for the current digit.
  • For each combination in the queue, we append each letter corresponding to the current digit, resulting in new combinations.
  • We repeat this process for each digit in the input digits.
  • Finally, we return the list of combinations after processing all digits.

Time Complexity:

  • The time complexity of this solution is O(4^n), where n is the length of the input digits string. This is because each digit can map to up to 4 letters, and for each digit, we perform an operation on each existing combination in the queue.

Space Complexity:

  • The space complexity is also O(4^n), as we store all possible combinations in the queue.

Here’s a Python implementation of the letter_combinations function using backtracking:

from typing import List

def letter_combinations(digits: str) -> List[str]:
    # Define the mapping of digits to letters
    digit_mapping = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    }
    
    # Initialize a list to store the resulting combinations
    combinations = []
    
    # Define a helper function for backtracking
    def backtrack(index: int, path: str):
        # If the path is of the same length as the input digits, add it to the combinations
        if len(path) == len(digits):
            combinations.append(path)
            return
        
        # Get the letters corresponding to the current digit
        letters = digit_mapping[digits[index]]
        
        # Iterate over each letter and make recursive calls for the next digit
        for letter in letters:
            backtrack(index + 1, path + letter)
    
    # Start backtracking from the first digit
    if digits:
        backtrack(0, "")
    
    return combinations

# Example usage:
print(letter_combinations("23"))  # Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
print(letter_combinations(""))    # Output: []
print(letter_combinations("2"))   # Output: ["a", "b", "c"]

Explanation:

  • We define a mapping digit_mapping that maps each digit to the corresponding letters on a phone keypad.
  • We initialize an empty list combinations to store the resulting combinations.
  • We define a helper function backtrack that takes an index representing the current digit and a path representing the current combination being constructed.
  • In the backtrack function, if the length of the path equals the length of the input digits, we add the path to the combinations.
  • Otherwise, we get the letters corresponding to the current digit, iterate over each letter, and make recursive calls to backtrack with the next digit and updated path.
  • We start backtracking from the first digit of the input digits string.
  • Finally, we return the list of combinations.

Time Complexity:

  • Since each digit can map to up to 4 letters, and we make recursive calls for each possible letter, the time complexity is O(4^n), where n is the length of the input digits string.

Space Complexity:

  • The space complexity is also O(4^n), as we store all possible combinations in the combinations list.