Letter Combinations of a Phone Number

Problem Description

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: []

Example 3:

Input: digits = "2" Output: ["a","b","c"]

Brute Force Solution

The brute force solution would involve generating all possible combinations of letters and then filtering out the ones that don't match the given digits. This is not an efficient approach.

Optimal Solution

The optimal solution uses a backtracking algorithm to generate the combinations. We iterate through the digits, and for each digit, we iterate through the corresponding letters. We build up a combination string and recursively call the function with the next digit. When we have processed all digits, we add the combination to the result.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

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

        result = []

        def backtrack(index, combination):
            if index == len(digits):
                result.append(combination)
                return

            digit = digits[index]
            letters = digit_to_letters[digit]

            for letter in letters:
                backtrack(index + 1, combination + letter)

        backtrack(0, "")
        return result

Big(O) Run-time Analysis

Let n be the number of digits in the input string digits. Let k be the maximum number of letters associated with a single digit (which is 4, corresponding to digits 7 and 9).

The number of possible combinations in the worst case is O(4^n), because each digit can have up to 4 possible letters.
The backtrack function is called recursively for each possible letter. The depth of the recursion is n.
Therefore, the time complexity is O(4^n * n). The n factor comes from the fact that we need to copy n characters to form each combination string.

Big(O) Space Usage Analysis

The space complexity is O(n) for the call stack due to the recursive calls of the backtrack function. The maximum depth of the call stack is n.
The result list stores the combinations. In the worst case, the number of combinations is O(4^n). Therefore, the space used by the result list is O(4^n * n). The n factor is because each string has length n.
Thus, the overall space complexity is O(4^n * n).

Edge Cases

Empty input: If the input string is empty, the function should return an empty list.
Invalid input: If the input string contains digits other than 2-9, the function should handle it gracefully (e.g., by ignoring the invalid digits or raising an exception). The provided solution assumes the input is valid.
Single digit input: If the input string contains only one digit, the function should return a list of the corresponding letters.

Given a digit string, return all possible letter combinations that the number could represent.