Letter Combinations of a Phone Number medium

Problem Statement

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. Note that 1 does not map to any letters.

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

Example 1

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

Example 2

Input: digits = "" Output: []

Steps

1. Base Case: If the input string digits is empty, return an empty array.
2. Mapping: Create a mapping from digits to their corresponding letters. We'll use a JavaScript object for this.
3. Recursive Approach: We'll use a recursive helper function to generate combinations.
   • Base Case (Recursive): If the current digit index is equal to the length of digits, it means we've processed all digits, so we add the current combination to the result array.
   • Recursive Step: Otherwise, get the letters corresponding to the current digit. For each letter, recursively call the helper function with the next digit index and append the letter to the current combination.
4. Return Result: The main function returns the array of generated combinations.

Explanation

The solution employs a backtracking approach. We explore all possible letter choices at each digit position. The recursive function builds up combinations one digit at a time. When it reaches the end of the digits string, a complete combination is formed and added to the result. Backtracking ensures that all combinations are explored without redundancy.

Code

function letterCombinations(digits: string): string[] {
    if (digits.length === 0) {
        return [];
    }

    const mapping: { [key: string]: string } = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',
    };

    const result: string[] = [];

    function backtrack(combination: string, index: number): void {
        if (index === digits.length) {
            result.push(combination);
            return;
        }

        const letters = mapping[digits[index]];
        for (let i = 0; i < letters.length; i++) {
            backtrack(combination + letters[i], index + 1);
        }
    }

    backtrack("", 0);
    return result;
}


//Example usage
console.log(letterCombinations("23")); // Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
console.log(letterCombinations("")); // Output: []
console.log(letterCombinations("2")); // Output: ['a', 'b', 'c']

Complexity

• Time Complexity: O(4^N * N), where N is the length of the input digits string. In the worst case, each digit can map to 4 letters. We need to explore all combinations, and constructing each combination takes O(N) time.
• Space Complexity: O(N) in the worst case due to the recursive call stack and the space needed to store the generated combinations (although the space for storing combinations can also be considered O(4^N) in the worst case, depending on how the results are stored).