algoadvance

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:

Example:

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

Clarifying Questions

  1. What is the length range of the input string?
    • The input length can vary from 0 to 4.
  2. Is it guaranteed that the input string will only contain digits from 2 to 9?
    • Yes, it’s guaranteed that only digits from 2 to 9 are present.
  3. Do we need to account for any special characters or non-digit characters in the input?
    • No, special characters or non-digit characters are not included.

Strategy

We’ll use a backtracking approach to solve this problem. Here’s a step-by-step strategy:

  1. Mapping Initialization: Create a dictionary to map each digit to its corresponding letters.
  2. Recursive Function (Backtracking): Define a recursive function that will build combinations of letters.
  3. Base Case: If the length of the accumulated combination matches the length of the digits input, append it to the result.
  4. Recursive Case: Iterate through the possible letters for the current digit, appending each letter to the current combination and recursively building the next part of the combination.
  5. Edge Case: If the input string is empty, immediately return an empty list.

Code

def letterCombinations(digits):
    if not digits:
        return []
    
    # Mapping from digit to corresponding letters
    phone_map = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl", 
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
    }
    
    result = []
    
    # Backtracking function
    def backtrack(index, path):
        # If the path length matches the digits length, we have a combination
        if index == len(digits):
            result.append("".join(path))
            return
        
        # Get letters that the current digit maps to
        possible_letters = phone_map[digits[index]]
        
        for letter in possible_letters:
            path.append(letter)  # Make a choice
            backtrack(index + 1, path)  # Explore with that choice
            path.pop()  # Undo the choice
    
    # Initiate backtracking
    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 this solution is O(4^n) where n is the length of the input digits. This is because each digit can map to at most 4 letters and we are generating all possible combinations. For each combination, we perform a certain fixed operation, leading to this complexity.

Space Complexity: The space complexity is also O(4^n) to store the result plus the space used by the recursion stack, which means in the worst case, it will take space proportional to the number of combinations.

Try our interview co-pilot at AlgoAdvance.com