LC-电话号码的字母组合

发表于 更新于 分类于

题目描述

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

1
2
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

代码实现

这也是一个典型的回溯算法应用

下面这段代码中使用了 for of 来进行循环，比 for 方便多了，因为 for 还要判断个数。同样，这里的 prefix.pop(); 和 prefix.join('') 需要格外注意。

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
26
27
28
29
30
31
32
33
34
35
/**
 * @param {string} digits
 * @return {string[]}
 */
const letters = {
  2: 'abc',
  3: 'def',
  4: 'ghi',
  5: 'jkl',
  6: 'mno',
  7: 'pqrs',
  8: 'tuv',
  9: 'wxyz'
};

var letterCombinations = function(digits) {
  let result = [];
  let prefix = [];
  if (digits.length) {
    backTracking(0);
  }

  function backTracking(index) {
    if (index === digits.length) {
      result.push(prefix.join(''));
      return;
    }
    for(let letter of letters[digits[index]]) {
      prefix.push(letter);
      backTracking(index + 1);
      prefix.pop();
    }
  }
  return result;
};