Letter Combinations Of A Phone Number

Mark as Completed

Lesson

Write a function called findLetterCombinations
that takes in a string of digits and returns an array of all possible letter combinations that can be formed from the digit string, based on the letters assigned to each digit on a phone keypad.

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

Walkthrough

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.

Previous Lesson Next Lesson