Letter Combinations of a Phone Number Medium 0 attempts
LeetCode ↗

Letter Combinations of a Phone Number

Medium Stack&Queue LeetCode

Given a string made up of digits 2 through 9, work out every letter combination it could spell, using the same digit-to-letter mapping found on an old telephone keypad (2 maps to abc, 3 to def, and so on through 9 mapping to wxyz). The combinations can come back in any order. An empty input string should simply produce an empty array of results.

Input Format
Implement letterCombinationsOfAPhoneNumber(digits). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. Result ordering is ignored.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
digits = ""
Output
[]
Constraints
  • 0 <= digits.length <= 4
  • digits[i] is in range ['2', '9']
Test Cases (2)
Case 1
Args: ["23"] Expected: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Case 2
Args: [""] Expected: []
Topics
Stack&Queue

Approach: Backtracking

Map each digit to its corresponding letters. Recursively build combinations by choosing one letter per digit and advancing to the next digit. When the current combination length equals the digits length, add it to the result.

javascript
function letterCombinationsOfAPhoneNumber(digits) {
  if (!digits.length) return [];
  const map = {2:"abc",3:"def",4:"ghi",5:"jkl",6:"mno",7:"pqrs",8:"tuv",9:"wxyz"};
  const result = [];
  function backtrack(i, curr) {
    if (i === digits.length) { result.push(curr); return; }
    for (const ch of map[digits[i]]) backtrack(i + 1, curr + ch);
  }
  backtrack(0, "");
  return result;
}

Time Complexity: O(n × 4^n) including output strings, where n is the length of digits

Space Complexity: O(n) for recursion depth

Saved in this browser only. Private to you.

JavaScript