17. 电话号码的字母组合

[swiftwind0405]

方法一：回溯法（DFS）

解题思想：

代码：

var letterCombinations = function (digits) {
  if (digits.length == 0) return [];

  const map = new Map(),
    res = [];
  // 初始化字典映射
  map.set("2", "abc");
  map.set("3", "def");
  map.set("4", "ghi");
  map.set("5", "jkl");
  map.set("6", "mno");
  map.set("7", "pqrs");
  map.set("8", "tuv");
  map.set("9", "wxyz");

  const dfs = (curStr, i) => {
    // 指针越界，递归的出口
    if (i > digits.length - 1) {
      // 将解推入res
      res.push(curStr);
      // 结束当前递归分支，进入另一个递归分支
      return;
    }

    const letters = map.get(digits[i]);
    // 不同的字母选择代表不同的递归分支
    for (const l of letters) {
      dfs(curStr + l, i + 1);
    }
  };
  dfs("", 0);
  return res;
};

复杂度分析：

• 时间复杂度：遍历所有节点，最坏的情况去到 O(4^n)，n 为数字串的长度。
• 空间复杂度：O(n)，递归栈调用的深度。

方法二：BFS

解题思想：
维护一个队列。
起初让空字符串入列，让当前层的字符串逐个出列，出列的字符串，会构建它下一层的新字母串，并入列。
一层层地，考察到数字串的最末位，就到了最底一层，此时队列中存的是所有构建完毕的字母串，返回 queue 即可。

和传统的BFS不同，这里控制了层序遍历的深度，等于 digits 的长度，而不是 while(queue.length){.. 那样让所有的节点入列出列，最后还会剩下最后一层节点，留在 queue 中返回。

代码：

const letterCombinations = (digits) => {
  if (digits.length == 0) return [];
  const map = {
    2: "abc",
    3: "def",
    4: "ghi",
    5: "jkl",
    6: "mno",
    7: "pqrs",
    8: "tuv",
    9: "wxyz",
  };

  const queue = [];
  queue.push("");
  for (let i = 0; i < digits.length; i++) {
    // bfs的层数，即digits的长度
    const levelSize = queue.length; // 当前层的节点个数
    for (let j = 0; j < levelSize; j++) {
      // 逐个让当前层的节点出列
      const curStr = queue.shift(); // 出列

      const letters = map[digits[i]];

      for (const l of letters) {
        queue.push(curStr + l); // 生成新的字母串入列
      }
    }
  }
  return queue; // 队列中全是最后一层生成的字母串
};

复杂度分析：

[swiftwind0405]

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/shou-hua-tu-jie-liang-chong-jie-fa-dfshui-su-bfsya/