0017-电话号码的字母组合.md

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

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

 

示例 1：

输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] 示例 2：

输入：digits = "" 输出：[] 示例 3：

输入：digits = "2" 输出：["a","b","c"]

var letterCombinations = function(digits) {
  const result = []
  if (digits.length === 0) {
    return result
  }
  const map = {
    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'],
  }
  const dfs = (str, nextStr) => {
    if (nextStr.length === 0) {
      result.push(str)
    } else {
      for (let key of map[nextStr[0]]) {
        dfs(`${str}${key}`, nextStr.substring(1))
      }
    }
  }
  dfs('', digits)
  return result
};

解题思路： 这里用到了动态规划，注意先维护一个映射去生成不同数字对应的字符数组，再使用动态规划函数逐级递归即可。