Leetcode 17 – Letter Combinations of a Phone Number

Description:

Given a string containing digits from 2 to 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.

Digit	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"]

Analysis:

This problem is essentially generating all possible combinations from the digit-to-letter mappings. Each digit can be mapped to 3-4 possible letters, and the goal is to generate all possible combinations using the provided digits.

To solve this problem, a recursive backtracking approach can be used. Starting from the first digit, we explore all possible letter choices, and then proceed to the next digit, combining the choices until we have generated all combinations.

Python Code:

def letterCombinations(digits: str):
    # Mapping of digits to corresponding letters
    phone_map = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    }

    # If the input is empty, return an empty list
    if not digits:
        return []

    # List to store the result combinations
    result = []

    # Backtracking function to generate combinations
    def backtrack(index, current_combination):
        # If the current combination is as long as the digits, add it to the results
        if index == len(digits):
            result.append(current_combination)
            return

        # Get the letters corresponding to the current digit
        current_digit = digits[index]
        letters = phone_map[current_digit]

        # Recursively generate all combinations
        for letter in letters:
            backtrack(index + 1, current_combination + letter)

    # Start the backtracking with an empty combination
    backtrack(0, "")

    return result

Example usage:

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

Time Complexity:

The time complexity of the solution is O(3^n × 4^m), where:

• n is the number of digits that map to 3 letters (2, 3, 4, 5, 6, 8).
• m is the number of digits that map to 4 letters (7, 9).

In the worst case, if all the digits map to 4 letters (like ‘7’ and ‘9’), there would be 4^m combinations to explore. However, since most digits map to 3 letters, the complexity varies based on the actual input. Therefore, a loose upper bound is O(4^n) where n is the length of the digits string.

Space Complexity:

• The space complexity is O(n) for storing the recursion stack, where n is the length of the input digits.
• Additionally, the space required to store the result list is O(4^n), where n is the length of the digits, as each combination is stored in the result.