Leetcode 17 - Letter combinations of a phone number

Note:

  • This is a backtracking problem.
  • Not like other combination sum questions. You are not just iterating a single string, instead, you are iterating many strings in responding to every digit of digits.
  • Three steps to do backtracking problems
    • The backtracking params are current index of digits and digits.
    • The termination condition is index === digits.length
    • The logic of iterating on each level is the most important part
      • Get the string according to index.
      • Do backtracking.

img

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.

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
let ans = [];
let path = [];
if (digits.length === 0) return ans;
let map = {'0':'', '1':'','2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'};
backtracking(0, digits);
return ans;

function backtracking(index, digits) {
if (index == digits.length) {
ans.push(path.join(''));
return;
}
const str = map[digits[index]];
for (let i = 0; i < str.length; i++) {
path.push(str[i]);
backtracking(index + 1, digits);
path.pop();
}
}
};