Problem Statement

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

• 2 -> abc
• 3 -> def
• 4 -> ghi
• 5 -> jkl
• 6 -> mno
• 7 -> pqrs
• 8 -> tuv
• 9 -> wxyz

Additional information

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

Example 1:

Input: digits = "23"

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

Example 2:

Input: digits = ""

Output: []

Example 3:

Input: digits = "2"

Output: ["a", "b", "c"]

Iterative Cross-Product (Brute Force)

Intuition

We can build the combinations iteratively by taking whatever combinations we currently have and multiplying them by the letters of the next digit.

Imagine we process the digits "23".

1. We start with an empty string: [""].
2. We look at the first digit "2", which maps to "abc". We append each letter to our existing string, resulting in ["a", "b", "c"].
3. We look at the next digit "3", which maps to "def". We take every string we built in step 2, and append each letter of "def" to them. "a" becomes "ad", "ae", "af". "b" becomes "bd", "be", "bf", and so on.

Algorithm

1. If the input digits is empty, immediately return an empty list [].
2. Create a dictionary digit_to_char to map the digits to their respective string of characters.
3. Initialize an array res with an empty string [""].
4. Loop through every digit in the digits string.
5. For each digit, create a temporary array new_res.
6. Loop through every character char mapped to that digit.
7. Loop through every existing combination in res, and append combination + char to new_res.
8. Update res = new_res to prepare for the next digit.
9. Return res.

def letter_combinations(digits: str) -> list[str]:
    if not digits:
        return []
        
    digit_to_char = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
    }
    
    res = [""]
    for digit in digits:
        new_res = []
        for char in digit_to_char[digit]:
            for combination in res:
                new_res.append(combination + char)
        res = new_res
        
    return res

Time & Space Complexity

• Time complexity: O(4^N * N)

• Reason: N is the length of the digits string. The maximum number of letters a digit can map to is 4 (for '7' and '9'). The number of combinations grows exponentially, up to 4^N. Appending characters to strings of length N takes O(N) time. Therefore, the total time is O(4^N * N).

• Space complexity: O(4^N * N)

• Reason: The res and new_res arrays need to store all 4^N combinations, and each combination is a string of length N.

Recursive Backtracking (DFS) - Optimal

Intuition

We can also formulate this as a decision tree and traverse it using Depth-First Search (DFS). This is arguably the most elegant way to solve combination/permutation problems.

At the very top of the tree, we look at the first digit. We branch off for every possible letter that digit represents. As we move down a branch, we look at the next digit, and branch off again. When our path length equals the number of input digits, we've hit a leaf node! We record the formed string and backtrack to explore other branches.

Algorithm

1. If the digits string is empty, return [].
2. Create the digit_to_char mapping dictionary.
3. Initialize an empty list res for the final combinations.
4. Create a recursive helper dfs(i, current_string) where i is the current index in the digits string.
5. Base Case: If i == len(digits), we have completely processed the input. Append current_string to res and return.
6. Recursive Step: Look up the letters for the current digit: letters = digit_to_char[digits[i]].
7. Loop through every char in letters.
8. Recursively call dfs(i + 1, current_string + char). (Notice that string concatenation automatically handles the backtracking process because strings are immutable in Python; it passes a fresh string down to the next level without modifying the current one).
9. Call dfs(0, "") to start the recursion.
10. Return res.

def letter_combinations(digits: str) -> list[str]:
    if not digits:
        return []
        
    digit_to_char = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
    }
    
    res = []
    
    def dfs(i, current_string):
        if i == len(digits):
            res.append(current_string)
            return
            
        for char in digit_to_char[digits[i]]:
            dfs(i + 1, current_string + char)
            
    dfs(0, "")
    return res

Time & Space Complexity

• Time complexity: O(4^N * N)

• Reason: The decision tree has a maximum branching factor of 4 and a depth of N. At each of the 4^N leaf nodes, creating the final string takes O(N) time.

• Space complexity: O(N)

• Reason: Excluding the output array, the auxiliary space used is strictly bounded by the maximum depth of the recursion stack, which equals the length of the digits string, O(N).