Letter Combinations of a Phone Number medium

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 digit 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

Example 1:

Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = "" Output: []

Steps

1. Base Case: If the input string digits is empty, return an empty list.
2. Mapping: Create a dictionary mapping digits to their corresponding letters.
3. Recursive Approach: We'll use backtracking (a recursive approach).
   • Start with an empty combination string.
   • Iterate through the digits. For each digit:
     • Get the corresponding letters from the mapping.
     • For each letter, append it to the current combination string.
     • Recursively call the function with the remaining digits.
     • After the recursive call returns, remove the last added letter (backtracking step). This allows exploration of other letter combinations.
4. Result: Collect all the complete combinations (strings with length equal to the length of digits) in a list and return it.

Explanation

The solution employs a depth-first search (DFS) strategy via recursion. Imagine a tree where each level represents a digit. At each level, the branches represent the possible letters for that digit. The algorithm explores all paths down the tree, generating all possible combinations. The backtracking step is crucial; it ensures that we explore all possible combinations without getting stuck in a single branch.

Code

def letterCombinations(digits):
    """
    Generates all possible letter combinations from a digit string.

    Args:
        digits: A string containing digits from 2-9.

    Returns:
        A list of strings representing all letter combinations, or an empty list if digits is empty.
    """

    if not digits:
        return []

    mapping = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    }

    result = []

    def backtrack(combination, next_digits):
        if not next_digits:
            result.append(combination)
            return

        digit = next_digits[0]
        letters = mapping[digit]
        for letter in letters:
            backtrack(combination + letter, next_digits[1:])

    backtrack("", digits)
    return result

#Example Usage
digits = "23"
print(letterCombinations(digits)) # Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

digits = ""
print(letterCombinations(digits)) # Output: []

digits = "2"
print(letterCombinations(digits)) # Output: ['a', 'b', 'c']

Complexity

• Time Complexity: O(4^N * N), where N is the length of the input digits string. In the worst case, each digit can map to 4 letters, and we need to create strings of length N. The N factor comes from string concatenation in each recursive call.
• Space Complexity: O(4^N * N) because of the space used to store the resulting combinations. In the worst case, we could have 4^N combinations, each of length N. The recursive call stack also contributes to the space complexity, but it is typically smaller than the space used to store the result. In essence, the space is dominated by the output.