给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

思路

  1. 维护 (数字 -> 字符组) 的字典
  2. 动态规划 dp[0] = [‘’]
  3. dp[n] = dp[n - 1] X [nums[n]] (笛卡尔积)
  4. 最终 dp[n] 即结果
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
var letterCombinations = function (digits) {
  if (digits.length === 0) {
    return []
  }
  const mapper = {
    2: 'abc',
    3: 'def',
    4: 'ghi',
    5: 'jkl',
    6: 'mno',
    7: 'pqrs',
    8: 'tuv',
    9: 'wxyz',
  }
  let curItems = ['']
  for (const num of digits) {
    const charList = mapper[num]
    let nextItems = []
    for (const char of charList) {
      nextItems = nextItems.concat(curItems.map((item) => item + char))
    }
    curItems = nextItems
  }
  return curItems
}