Letter Combinations of a Phone Number - Python Solution

1. Introduction

The "Letter Combinations of a Phone Number" problem is a classic example of a combinatorial problem often encountered in coding interviews. The challenge is to generate all possible letter combinations that a given number could represent based on the mappings found on a telephone keypad.

Problem

Given a string containing digits from 2-9, find all possible letter combinations that these digits could represent, similar to the letters mapped on a telephone keypad. Note that the digit 1 does not map to any letters.

2. Solution Steps

1. Create a mapping of digits to their corresponding letters.

2. Use a recursive function to generate combinations.

3. For each digit, iterate through its mapped letters and append them to the current combination.

4. Recurse with the next digit until all digits are processed.

5. Add the completed combination to the result list.

3. Code Program

# Function to generate letter combinations
def letterCombinations(digits):
    if not digits:
        return []

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

    # Recursive function to build combinations
    def backtrack(index, path):
        # If the path is the same length as digits, we have a complete combination
        if len(path) == len(digits):
            combinations.append("".join(path))
            return

        # Get the letters that the current digit maps to, and loop through them
        possible_letters = phone_map[digits[index]]
        for letter in possible_letters:
            # Add the letter to our current path
            path.append(letter)
            # Move on to the next digit
            backtrack(index + 1, path)
            # Backtrack, remove the letter from our path
            path.pop()

    # List to hold the combinations
    combinations = []
    backtrack(0, [])
    return combinations

# Testing the function
print(letterCombinations("23"))

Output:

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

Explanation:

In this solution, we first define a mapping from digits to their corresponding letters, similar to a phone keypad. 

The letterCombinations function takes a string of digits and uses a helper function backtrack to form combinations. 

The backtrack function recursively builds combinations of letters. When the length of the current combination (path) matches the length of the input digits, a complete combination is added to the result list. The function finally returns all the possible letter combinations.