[LeetCode] 17. Letter Combinations of a Phone Number

Table of Contents

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 digit 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 \leq \text{digits.length} \leq 4$
• digits[i] is a digit in the range ['2', '9'].

Approach

We build the letter combinations sequentially by iterating through the input digits and appending the corresponding letters for each digit to the combinations generated so far.

• For the first digit, the possible combinations are simply its mapped letters.
• For each subsequent digit, we take every combination already built and append each letter corresponding to the current digit.

This results in all possible letter combinations for the input digit string.

Solution

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  // Map digits to corresponding letters
  const charMap = {
    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"],
  };

  // Use reduce to accumulate letter combinations for each digit
  return [...digits].reduce((combinations, digit) => {
    const chars = charMap[digit];

    // If the digit is not in the map, skip processing it
    if (!chars) return combinations;

    // If there are no combinations yet, start with the current digit's letters
    if (!combinations.length) return charMap[digit];

    // For every existing combination, append each character from the current digit.
    return combinations.reduce(
      (acc, combination) => [...acc, ...chars.map(char => combination + char)],
      []
    );
  }, []);
};

Complexity Analysis

Time Complexity

The time complexity is $O(3^m \times 4^n)$, where $m$ is the number of digits that map to 3 letters (e.g., 2, 3, 4, 5, 6, 8) and $n$ is the number of digits that map to 4 letters (e.g., 7, 9). The total number of combinations is the product of the number of letters for each digit.

Space Complexity

The space complexity is $O(3^m \times 4^n)$, where $m$ is the number of digits that map to 3 letters and $n$ is the number of digits that map to 4 letters. The space complexity is determined by the number of possible combinations.