Lt46. 全排列、77. 组合、17. 电话号码的字母组合

46. 全排列

给定一个**  没有重复** 数字的序列，返回其所有可能的全排列。
示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路

使用回溯法，当临时数组长度等于 k 时，得到了一种排列方式，将 temp 加入结果 res 数组。
每次 dfs 都会从下标 0 开始找起，使用一个 visited 数组判断，求一种排列方式的过程中，数组内的元素的访问状态，在 temp 中有的数据，会被设为 true。下一个 dfs 会跳过 temp 中已有的元素。
dfs 完成后，将 temp 出栈，同时将 visited 设回未访问状态。

解答

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const res = [];
  const temp = [];
  let visited = Array(nums.length).fill(false);
  const dfs = () => {
    if (temp.length === nums.length) {
      res.push(temp.slice());
      return;
    } else {
      for (let i = 0; i < nums.length; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        temp.push(nums[i]);
        dfs(temp);
        visited[i] = false;
        temp.pop();
      }
    }
  };
  dfs();
  return res;
};

77. 组合

给定两个整数 n 和 k_，返回 1 … *n *中所有可能的 _k 个数的组合。
示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

思路

和全排列方法类似，但是组合不需要从 0 开始找起，之前的元素是已经在当前组合或其他情况组合里的，所以 dfs 可以传入当前元素下标，从当前元素的下一个开始进行组合。

解答

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
  const res = [];
  const temp = [];
  const dfs = (x) => {
    if (temp.length === k) {
      res.push(temp.slice());
      return;
    } else {
      for (let i = x + 1; i <= n; i++) {
        temp.push(i);
        dfs(i);
        temp.pop();
      }
    }
  };
  dfs(0);
  return res;
};

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

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

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

思路

两两组合-BFS

本质上是 BFS 实现的回溯，一层一层得到每层可以组合的结果，可以使用队列再优化。写一个两个数组的组合的方法，再将结果和下一个数组进行求组合。先删除字符串中的 1，之后如果没有长度或字符等于 1 返回空数组，其他情况返回对应的 map 里的数组。长度大于 2 的进行组合求解。

DFS

使用一个 x，x 表示使用原字符串的指针下标，其实也可以不使用，直接使用临时数组长度 temp.length 代替 x。使用map[digits[x]]得到当前指针下标对应 map 里的数组，按顺序选取一个字符插入临时数组中，再进行 dfs 传入 x+1，对下一位进行处理，如果 x 等于 digits 长度则处理完成，将结果添加到 res 中，返回。处理完以后将当前字符出栈，选取下一个字符加入。

解答

两两组合-BFS

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  digits = digits.replace(/1/g, "");
  if (!digits.length || digits === "1") return [];
  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"],
  };
  if (digits.length === 1) return map[digits];
  const combine = (arr1, arr2) => {
    const res = [];
    const temp = [];
    for (let i = 0; i < arr1.length; i++) {
      temp.push(arr1[i]);
      for (let j = 0; j < arr2.length; j++) {
        temp.push(arr2[j]);
        res.push(temp.slice().join(""));
        temp.pop();
      }
      temp.pop();
    }
    return res;
  };
  return digits.split("").reduce((a, b) => {
    if (a instanceof Array) return combine(a, map[b]);
    else return [].concat(combine(map[a], map[b]));
  });
};

DFS

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  digits = digits.replace(/1/g, "");
  if (!digits.length || digits === "1") return [];
  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"],
  };
  if (digits.length === 1) return map[digits];
  const temp = [];
  const res = [];
  const dfs = (x) => {
    if (x === digits.length) {
      res.push(temp.slice().join(""));
      return;
    } else {
      for (let i = 0; i < map[digits[x]].length; i++) {
        temp.push(map[digits[x]][i]);
        dfs(x + 1);
        temp.pop();
      }
    }
  };
  dfs(0);
  return res;
};