maw.sh > Mahmoud Ashraf Website

SupportPalestine

17. Letter Combinations of a Phone Number 🔗

Date: Jun 11, 2024

Tags: backtracking

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 digits 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 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

Optimal (Backtracking)

type Digits = '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';

const mobile = {
  '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'],
};

function letterCombinations(digits: string): string[] {
  if (digits.length === 0) return [];

  const result: string[] = [];

  function backtrack(index: number, path: string) {
    if (path.length === digits.length) {
      result.push(path);
      return;
    }

    for (const letter of mobile[digits[index] as Digits]) {
      backtrack(index + 1, path + letter);
    }
  }

  backtrack(0, '');

  return result;
}

export { letterCombinations };