17. Letter Combinations of a Phone Number

Difficulty: MEDIUM

Problem description can be found here.

Approach

Can follow a typical Backtracking problem template.

Need to find out what is the “iterator”, which in this case you only iterate the values as specified in the digits.

“23” —> only takes “abc” and “def”, other key value pairs in the hashmap can be ignored.

Solution

const mapping = {
  "2": "abc",
  "3": "def",
  "4": "ghi",
  "5": "jkl",
  "6": "mno",
  "7": "pqrs",
  "8": "tuv",
  "9": "wxyz",
};

function letterCombinations(digits: string): string[] {
  const result: string[] = [];

  if (digits === "") return [];

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

    for (const char of mapping[digits[index] as keyof typeof mapping]) {
      backtrack(index + 1, path + char);
    }
  }

  backtrack(0, "");

  return result;
}