Finding All Letter Combinations from Digits Mapped Like Phone Buttons

Want to know how phone digits can make letter combinations? Let’s solve it step by step using simple JavaScript (LeetCode 17).

We are given a string containing digits from 2 to 9 inclusive, and need to find all possible letter combinations that the digits could represent, based on a phone keypad mapping. The given string can have a length from 0 to 4.

How the letters are mapped by digits can be seen in the image below.

We will solve this problem by using recursion and backtracking through JavaScript. Let's say the function below is given for solving this problem:

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {

}

First of all, we create an array result to store the possible combinations, and return it if the given string has zero length. Then we create an object that maps digits to their representative letters at the top of the letterCombinations function.

    const result = [];
    if (!digits || digits.length === 0) return result;

    const lettersMap = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
    };

Then we create a recursive function that has two parameters: first is builder – an array to store the letters of a combination, and second is index – used to get digits from the given string one by one.

    const nextDigit = (builder, index) => {

    };

In the nextDigit function, we first check if the index is equal to digits.length, then push the combination formed by joining the letters of the builder array and return.

// At top under nextDigit function
if (index === digits.length) {
    result.push(builder.join(""));
    return;
}

Now we do the main work in the nextDigit function, which is getting letters for a digit, looping through its characters, and making possible combinations by calling nextDigit recursively and backtracking the builder array on each combination formed.

// After checking index === digits.length in nextDigit function
const letters = lettersMap[digits[index]];
for (let ch of letters) {
    builder.push(ch);
    nextDigit(builder, index + 1);
    builder.pop();
}

Finally, we call this recursive function to start the recursion and return the result array that contains all possible combinations. So the final full code for solving this problem is as below:

var letterCombinations = function(digits) {
    const result = [];
    if (!digits || digits.length === 0) return result;

    const lettersMap = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
    };
    
    const nextDigit = (builder, index) => {
        if (index === digits.length) {
            result.push(builder.join(""));
            return;
        }
        const letters = lettersMap[digits[index]];
        for (let ch of letters) {
            builder.push(ch);
            nextDigit(builder, index + 1);
            builder.pop();
        }
    };
    nextDigit([], 0);
    return result;
};

How this recursive code works, we can understand by the points below:

• Let's say digits = "23", we call nextDigit([], 0).
• The if condition will not run as index (0) is not equal to digits length (2).
• Now, letters = "abc" for index 0.
• In the first loop iteration, ch = "a", we push it into builder, now builder = ["a"].
• Next, we call nextDigit again with this builder and index = 1.
• This time again, the if condition won't run. We get letters = "def", push character 'd' into builder and call nextDigit again with builder = ["a", "d"] and index = 2.
• This time, the if condition runs. We push the first combination "ad" by joining the builder array, and return from this call.
• The next line that runs is builder.pop(), so builder becomes ["a"] and now the first iteration for letters "abc" at index 0 completed.
• Similarly, the if condition runs on every completion of a combination and pushes it into the result.
• So in this way, we add all possible combinations by recursion and backtracking.

Now we have successfully solved this problem. I hope you enjoyed the journey of solving this problem by recursion and backtracking with me, and learned some meaningful coding logic and improved your problem-solving skills.

Thanks for reading, Happy Coding!