Letter Combinations of a phone number

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 digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

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

Example 2:

Input: digits = ""
Output: []

Example 3:

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

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

Mapping of Digits to Letters:

The digits map to letters on a telephone button as follows:

• 2: “abc”
• 3: “def”
• 4: “ghi”
• 5: “jkl”
• 6: “mno”
• 7: “pqrs”
• 8: “tuv”
• 9: “wxyz”

Approach:

1. Handle Edge Cases: If the input string is empty, return an empty list since there are no digits to map.
2. Backtracking: This problem can be approached using backtracking. For each digit in the string, consider all possible letters it can represent and combine them recursively with the combinations of the remaining digits.
3. Recursive Function: Define a recursive function that constructs the combinations by appending letters mapped from the current digit and then recursively processing the next digit.
4. Base Case: When the current combination reaches the length of the input digits, add it to the result list.

def letterCombinations(digits):
    if not digits:
        return []
    
    # Mapping of digits to corresponding letters
    phone_map = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    
    # List to hold the result combinations
    result = []
    
    # Backtracking function to generate combinations
    def backtrack(index, path):
        # If the path is the same length as digits, we have a complete combination
        if index == len(digits):
            result.append(path)
            return
        
        # Get the letters corresponding to the current digit
        letters = phone_map[digits[index]]
        
        # Loop through each letter and recurse
        for letter in letters:
            backtrack(index + 1, path + letter)
    
    # Start backtracking from the first digit
    backtrack(0, "")
    
    return result

# Example usage:
print(letterCombinations("23"))  # Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
print(letterCombinations(""))    # Output: []
print(letterCombinations("2"))   # Output: ['a', 'b', 'c']

Explanation:

• Backtracking: We use backtracking to explore all possible combinations. Starting from the first digit, we append each possible letter to the current path and move to the next digit until the path is complete.
• Base Case: When the current path length equals the length of the input digits, we have formed a valid combination, and it is added to the result list.

Example:

For the input digits = "23", the possible combinations are:

• "a" from 2 and "d", "e", "f" from 3 result in: ["ad", "ae", "af"]
• "b" from 2 and "d", "e", "f" from 3 result in: ["bd", "be", "bf"]
• "c" from 2 and "d", "e", "f" from 3 result in: ["cd", "ce", "cf"]

Thus, the output is ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Also Read

Complexity:

• Time Complexity: O(4^n) where n is the length of the input digits. This is because each digit can map to up to 4 letters.
• Space Complexity: O(n) for the recursion stack in the worst case where n is the number of digits.