Letter Combinations of a Phone Number

 

  1. Clarify the problem:

    • The problem requires us to generate all possible letter combinations that can be formed by the digits of a phone number.
    • The mapping of digits to letters is given as a dictionary.
    • We need to return a list of all possible letter combinations.
    • The input phone number can contain digits from 2 to 9 inclusive.
    • The order of the letter combinations in the output does not matter.
    • The length of the phone number can range from 0 to 4 digits.

  2. Analyze the problem:

    • Input: A string representing a phone number.
    • Output: A list of all possible letter combinations.
    • Constraints:
      • The input phone number can contain digits from 2 to 9 inclusive.
      • The length of the phone number can range from 0 to 4 digits.

  3. Design an algorithm:

    • We can solve this problem using a recursive approach.
    • We define a recursive function that takes the current digit index, the current combination, and the final result list as parameters.
    • In the recursive function, we check the base case:
      • If the current digit index is equal to the length of the phone number, we have completed a valid combination. We append it to the result list and return.
    • For the current digit, we get the corresponding letters from the digit-letter mapping dictionary.
    • For each letter, we append it to the current combination and recursively call the function with the next digit index.
    • After the recursive call, we remove the last letter from the current combination to backtrack and explore other possibilities.
    • We start the recursion with an empty combination and an index of 0.
    • Finally, we return the result list containing all the valid combinations.

  4. Explain your approach:

    • We will use a recursive approach to generate all possible letter combinations.
    • We will define a recursive function that takes the current digit index, the current combination, and the final result list as parameters.
    • In the function, we check the base case: if the current digit index is equal to the length of the phone number, we have completed a valid combination, so we append it to the result list and return.
    • For the current digit, we get the corresponding letters from the digit-letter mapping dictionary.
    • For each letter, we append it to the current combination and recursively call the function with the next digit index.
    • After the recursive call, we remove the last letter from the current combination to backtrack and explore other possibilities.
    • We start the recursion with an empty combination and an index of 0.
    • Finally, we return the result list containing all the valid combinations.

  5. Write clean and readable code:

python
def letterCombinations(digits):
    if not digits:
        return []

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

    combinations = []
    generate_combinations(digits, '', 0, digit_map, combinations)
    return combinations

def generate_combinations(digits, current_combination, index, digit_map, combinations):
    if index == len(digits):
        combinations.append(current_combination)
        return

    current_digit = digits[index]
    letters = digit_map[current_digit]

    for letter in letters:
        new_combination = current_combination + letter
        generate_combinations(digits, new_combination, index + 1, digit_map, combinations)
  1. Test your code:
python
print(letterCombinations('23'))  # Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
print(letterCombinations('79'))  # Output: ['pw', 'px', 'py', 'pz', 'qw', 'qx', 'qy', 'qz', 'rw', 'rx', 'ry', 'rz', 'sw', 'sx', 'sy', 'sz']
print(letterCombinations('2'))  # Output: ['a', 'b', 'c']
print(letterCombinations(''))  # Output: []

  1. Optimize if necessary:

    • The recursive approach used has a time complexity of O(4^N), where N is the length of the phone number.
    • The space complexity is also O(4^N) due to the recursion stack and the output list.

  2. Handle error cases:

    • The code already handles the case where the input is an empty string by returning an empty list.

  3. Discuss complexity analysis:

    • Time complexity: O(4^N), where N is the length of the phone number.
    • Space complexity: O(4^N) due to the recursion stack and the output list.
Next Post Previous Post