Lesson

Write a function called `findLetterCombinations`

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

To solve this problem, we will use a depth-first search algorithm, which includes recursion, to traverse a tree or a graph. The general idea is to build a map that stores each potential number (i.e., digits 0-9) and the possible letters that can be made from it, based on the letters assigned to each digit on a phone keypad. Then, we will loop through each digit in the input string, get the corresponding possible letters from the map, and loop through each possible letter to form all possible combinations.

```
function findLetterCombinations(digits) {
// Define a map to store the possible letters for each digit
const map = new Map([
["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"]],
]);
// Handle the edge case of an empty input
if (digits.length === 0) {
return [];
}
// Define an array to store the possible combinations
let combinations = [""];
// Loop through each digit in the input string
for (let i = 0; i < digits.length; i++) {
const digit = digits[i];
const letters = map.get(digit);
// Skip the loop if the digit is invalid
if (!letters) {
continue;
}
// Define a temporary array to store the new combinations
const temp = [];
// Loop through each letter for the current digit
for (let j = 0; j < letters.length; j++) {
const letter = letters[j];
// Loop through each existing combination
for (let k = 0; k < combinations.length; k++) {
const combination = combinations[k];
// Add the new letter to the current combination
temp.push(combination + letter);
}
}
// Update the combinations array with the new combinations
combinations = temp;
}
// Return the final array of combinations
return combinations;
}
```

**Big O Complexity Analysis:**
The time complexity of this solution is O(4^n), where n is the length of the input string, because each digit can map to up to 4 letters and we have to loop through each digit in the input string to form all possible combinations. The space complexity is also O(4^n), because we have to store all possible combinations in an array. However, the space complexity can be optimized to O(n) by using recursion instead of loops, which would avoid storing all combinations in an array.