Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. 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_mapping = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz'
}

Function Signature:

from typing import List

def letter_combinations(digits: str) -> List[str]:
    """
    Return all possible letter combinations of the given string of digits.

    Parameters:
    - digits: A string containing digits from '2' to '9'.

    Returns:
    - List[str]: List of all possible letter combinations.
    """
    # Your code here

Example:

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

# Input: digits = ""
# Output: []

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

Note:

  • Although the above answer is in lexicographical order, your answer could be in any order you want.

Instructions:

  • Write the letter_combinations function to solve the problem above.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊