17. Letter Combinations of a Phone Number

Letter Combinations of a Phone Number

Problem Description

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'].

Approach) Brute Force

The way these solution works is to first loop through the digits provided to the function. For each digit, we then loop through the possibilities found on the previous digit. Finally, we loop through the characters available for the current digit.

This series of loops allows us to add all available combinations for each digit, taking combinations for previous digits into account, and is almost exactly how you might process the question as a human.

Code:

var mapOfNumbers = {
    2: ['a', 'b', 'c'],
    3: ['d', 'e', 'f'],
    4: ['g', 'h', 'i'],
    5: ['j', 'k', 'l'],
    6: ['m', 'n', 'o'],
    7: ['p', 'q', 'r', 's'],
    8: ['t', 'u', 'v'],
    9: ['w', 'x', 'y', 'z'],
};

var letterCombinations = function (digits) {
    // Return early if no digits were supplied
    if (!digits.length) {
        return [];
    }

    // Initialise an array to store all possible letter combinations up to the previous digit
    let lastDigitPossibilities = [''];

    // Loop through each digit
    for (let i = 0; i < digits.length; i++) {
        // Initialise an array to store the possibilties for this digit
        let newPossibilities = [];

        // Loop through the last set of possibilities
        for (let x = 0; x < lastDigitPossibilities.length; x++) {
            // Loop through the possible letters for the current number
            for (let letter of mapOfNumbers[digits[i]]) {
                // Add the current number to each of the last set of possibilities
                newPossibilities.push(lastDigitPossibilities[x].concat(letter));
            }
        }

        // Check if this was the last digit
        if (i == digits.length - 1) {
            // Return the latest batch of possibilities as the answer
            return newPossibilities;
        }

        lastDigitPossibilities = newPossibilities;
    }
};

Approach) Recursion

This solution isn’t all that different from the triple-loop one discussed above but might be a little easier to read if you’re big on recursive functions.

What we do is that we take the digits passed in, find out all the possible combinations for the first digit, and then call the function again on the remaining digits. Each time, we pass in all combinations found so far, which means that by the end, we have an array of all possible combinations.

Code:

var mapOfNumbers = {
    2: ['a', 'b', 'c'],
    3: ['d', 'e', 'f'],
    4: ['g', 'h', 'i'],
    5: ['j', 'k', 'l'],
    6: ['m', 'n', 'o'],
    7: ['p', 'q', 'r', 's'],
    8: ['t', 'u', 'v'],
    9: ['w', 'x', 'y', 'z'],
};

var letterCombinations = function (digits) {
    // Return early if no digits were supplied
    if (!digits.length) {
        return [];
    }

    function getLetterCombinations(digits, previousCombinations) {
        // Initialise an array to store the possibilties for this digit
        let newPossibilities = [];

        // Loop through the previous iteration's combinations
        for (let previousCombination of previousCombinations) {
            // Loop through the possible letters for this number
            for (let possibleLetter of mapOfNumbers[digits[0]]) {
                // Add a combination of the previous set with the current letters to the array
                newPossibilities.push(
                    previousCombination.concat(possibleLetter)
                );
            }
        }

        // If there are more digits, run the function again, otherwise return the combinations
        return digits.length > 1
            ? getLetterCombinations(digits.slice(1), newPossibilities)
            : newPossibilities;
    }

    return getLetterCombinations(digits.toString(), ['']);
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #17. Letter Combinations of a Phone Number

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!