Leetcode #17

Everything here will be done in JavaScript since it's my language of choice, but the ideas covered in this post can be implemented in nearly all languages.

First Intuition

After reading the problem description, my first intuition was to create a mapping for all letters corresponding to the digits on a phone keypad. Since the digits 0 and 1 don't map to any letters, their indices remain empty in the array.

const phoneMap = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];

From here, the goal is to generate all possible combinations of letters for the given input digits. To simplify, let's start by handling just the first digit.

const letters = phoneMap[digits[0]];
for (const letter of letters) {
    console.log(letter); // temp
}

So far, we are just looping through each of the letters corresponding to the digit inputted. If it was a "2", then we should see our function output to the console "a", "b", and "c". This is a start but obviously not what we want. What we need from here is to loop through the 2nd digit (if it exists), then the 3rd digit (if it also exists), and so on. You might think of solving this with nested loops for each digit.

However, instead of using nested loops, we should consider creating a recursive function. Recursive functions are often a better choice when dealing with repetitive tasks, like iterating through combinations. For now, let's place our existing loop in a function we'll call recursion.

function recursion() {
    const letters = phoneMap[digits[0]];
    for (const letter of letters) {
        console.log(letter); // temp
    }
}

Recursion

To make this a recursive function, it needs to call itself or return a result depending on a condition. The condition here will be how many character digits are left to process in the input string. For the input "23", we start by looping through the characters for the first digit ("2"). After processing the first digit, we can remove it from the string, leaving "3". Then, we process "3" and concatenate its letters with each of the letters from "2".

An example of this in action to better understand should look something like this:

1. Start with "23" for example

2. Take the first character digit "2"

3. Get it's corresponding letters ["a", "b", "c"]

4. Loop through these letters, starting with "a"

5. If there are any remaining digits (in this case, "3"), call the function again with the remaining digits. Concatenating the current letter ("a") with each letter from "3" (["d", "e", "f"]), forming combinations like "ad", "ae", and so on

6. Once there are no more remaining digits, push the combination into the output array. ["ad"]

7. Repeat this process for all possible combinations, resulting in the output array: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Now, let’s enhance our recursive function by adding currentCombination and remainingDigits as arguments:

function recursion(currentCombination, remainingDigits) {
    const letters = phoneMap[remainingDigits[0]];
    for (const letter of letters) {
        //console.log(letter);
    }
}

Next, we check if there are any digits left in the remainingDigits string. If there are, we call the recursive function within the loop, passing the updated currentCombination and the remainingDigits (excluding the first digit).

function recursion(currentCombination, remainingDigits) {
    if (remainingDigits.length) {
        const letters = phoneMap[remainingDigits[0]];
        for (const letter of letters) {
            recursion(combination + letter, remainingDigits.slice(1));
        }
    }
}

Finally, when remainingDigits.length is 0, we push the completed combination to the output array.

const output = [];

function recursion(currentCombination, remainingDigits) {
    if (remainingDigits.length) {
        const letters = phoneMap[remainingDigits[0]];
        for (const letter of letters) {
            recursion(currentCombination + letter, remainingDigits.slice(1));
        }
    } else {
        output.push(currentCombination);
    }
}

Finishing Touches

We're almost done! There’s one edge case to handle: if an empty string is input, the function should return an empty array. This can be achieved with a simple check at the start of the function.

var letterCombinations = function(digits) {
    if (!digits.length) return []; // early exit

    const phoneMap = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    const output = [];
    recursion("", digits) // start with an empty string and all remaining digits
    return output;

    function recursion(currentCombination, remainingDigits) {
        if (remainingDigits.length) { // test if there are any remaining digits
            const letters = phoneMap[remainingDigits[0]]; // get the corresponding letters for the left most digit
            for (const letter of letters) { // for each letter...
                recursion(currentCombination + letter, remainingDigits.slice(1)); // call the function again with the next digits
            }
        } else {
            output.push(currentCombination); // push this finished combination to the output array
        }
    }
};

This completes our function! It now generates all possible combinations of letters for any input string of digits while efficiently handling edge cases.