LeetCode Solutions Blog

Letter Combinations of a Phone Number

Number: 17

Difficulty: Medium

Paid? No

Problem Description

Given a string containing digits from "2" to "9", return all possible letter combinations that the number could represent using the mapping of digits to letters as on a telephone keypad. If the input string is empty, return an empty list.

Key Insights

Use a mapping from digits to the respective letters as defined by a telephone keypad.
Backtracking is an ideal approach to generate all possible combinations.
Each digit adds a level in the recursive tree where you append one letter at a time.
Handling edge cases such as an empty input string is crucial.

Space and Time Complexity

Time Complexity: O(4^n * n) where n is the length of the input string (each digit may map to up to 4 letters and adding a combination takes O(n) time). Space Complexity: O(n) for the recursion call stack, not counting the space required for storing the output.

Solution

We can solve the problem using a backtracking algorithm. First, we define a dictionary mapping each digit to its corresponding letters. Then we initiate a recursive function called backtrack that takes the current combination and the index of the next digit to process. At each call, if the combination is complete (length equal to the input string), we add it to the result list. Otherwise, we iterate through the letters corresponding to the current digit, append a letter to the combination, and recursively call backtrack with the next index. This approach ensures that all possible letter combinations are generated.

Code Solutions

# Python solution for Letter Combinations of a Phone Number

def letterCombinations(digits):
    # Mapping of digits to corresponding letters
    digit_to_letters = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz"
    }
    
    # If input is empty, return an empty list
    if not digits:
        return []
    
    result = []
    
    # Backtracking function to generate combinations
    def backtrack(index, current_combination):
        # If the current combination length equals the digits length,
        # add the combination to the result list.
        if index == len(digits):
            result.append(current_combination)
            return
        
        # Get the corresponding letters for the current digit
        letters = digit_to_letters[digits[index]]
        # Explore all possible letter routes for the current digit.
        for letter in letters:
            backtrack(index + 1, current_combination + letter)
    
    # Initiate backtracking starting from index 0 and empty combination.
    backtrack(0, "")
    return result

# Example usage:
#print(letterCombinations("23"))