实现数组的全排列和单词搜索

实现数组的全排列
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例
1
给定 numbs = [1,2,3];
2
​
3
返回
4
[
5
  [1,2,3],
6
  [1,3,2],
7
  [2,1,3],
8
  [2,3,1],
9
  [3,1,2],
10
  [3,2,1]
11
]
Copied!
方法一 回溯法
思路
回溯法通常是构造一颗生成树，生成树排列法的核心思想为： 遍历需要全排列的数组，不断选择元素，将不同的数字生成一颗树，如果数组中待选择的结点数为 0，则完成一种全排列。
详解
从上面的思路中，我们可以抽象出全排列函数的步骤：
1
1. 遍历需要全排列的数组，取出不同位置的数字，创建以对应位置数字为根节点的树。
2
​
3
2. 遍历剩下的数组，选出一个数字，将该数字挂在生成的树上。
4
​
5
3. 重复第二步操作直到剩余数字数组的长度为0，表明完成了全排列，将生成的树存入排序结果数组中。
Copied!
举个例子：输入数组为 [1, 2, 3]，首先选择 1 为根节点，剩余数组为 [2, 3]，继续选择 2 作为下一个结点，剩余数组为 [ 3 ]，那么选择 3 为最后一个结点，那么 [1, 2, 3] 组成一种全排列情况。 我们回溯到第二步剩余数组，选择 3 为第二个结点，那么剩余数组为 [ 2 ]，选择后完成 [1, 3, 2] 这种全排列情况。后续依次固定 2，3 为根结点，列出所有可能。
从上述内容中可以看出，生成初始树后就是一个 截取数组 -> 设置节点，继续 截取节点 -> 设置节点 的递归过程了。那么我们是否可以将第一步的操作合并到我们的递归函数中呢？
既然我们递归的操作是截取数字，并将对应的数字与目标树结合。那么我们可以将第一步看为数字和空树结合。
那么我们递归函数的参数就确定为：
剩余的数组
现有的顺序树
递归函数的逻辑也可以收敛为：
1.遍历需要全排列的数组，将不同位置的数字与目前树结合起来
2.重复该操作直到需要全排列的数组长度为 0，即表明完成了全排列。
代码
1
const permute = function (numbs) {
2
  const allSortResult = []; // 设置结果数组
3
  function recursion (restArr, tempResult) {
4
    for (let index = 0; index < restArr.length; index++) {
5
      // 获取不同位置的数字
6
      const insertNumb = restArr[index];
7
​
8
      // 将不同位置的数字与现有的顺序树相结合
9
      const nextTempResult = [...tempResult, insertNumb];
10
​
11
      /**
12
       * 判断传入的数组长度
13
       * 大于1:
14
       * 继续递归，参数分别为：
15
       *  1. 除去当前数字外的数组
16
       *  2. 新生成的树
17
       * 等于1(不会出现小于1的情况):
18
       *  表明已经结合到了最后一个节点，将生成的顺序树推送到结果数组中
19
       */
20
      if (restArr.length > 1) {
21
        recursion(
22
          restArr.filter(resetNumb => resetNumb !== insertNumb),
23
          nextTempResult
24
        );
25
      } else {
26
        allSortResult.push(nextTempResult);
27
      }
28
    }
29
  }
30
​
31
  // 调用递归方法，开始生成顺序树
32
  recursion(numbs, []);
33
​
34
  // 返回全排列结果
35
  return allSortResult;
36
};
Copied!
复杂度分析
时间复杂度：O(n2)O(n^2)O(n2)
​
空间复杂度：O(n2)O(n^2)O(n2)
​
方法二 插值排序法
思路
插值排列法的核心思想为： 遍历需要全排列的数组，将不同位置的数字抽离出来，插入到剩余数组的不同位置，即可得到该数字与另一个数组的全排列结果。 将一个固定的数字，插入到另一个数组的全排列结果的不同位置， 遍历需要全排列的数组，将不同的数字连接到不同的树上 继续全排列剩下的数组与生成的树，当剩余数组长度为0时，表明完成了全排列。
详解
从上面的思路中，我们可以抽象出插值排序全排列方法的具体实现：
首先处理特殊情况。如果传入排列的数组长度为1，直接返回该数组。否则进行下面的全排列方法
1
  1. 截取传入数组的第 1 位数字，将剩余数组传入获取全排列方法函数，获取剩余数字的全排列结果
2
​
3
  2. 遍历剩余数字的全排列结果数组并取出各个结果
4
​
5
  3. 使用循环将截取的数字插入到不同结果(数组)的不同位置，生成新的全排列结果并保存
6
​
7
  4. 返回全排列结果数组
Copied!
代码
1
const permute = function (numbs) {
2
  // 设定保存结果变量
3
  const result = [];
4
​
5
  // 如果长度为1，只有一种排列，直接返回
6
  if (numbs.length === 1) {
7
    return [numbs];
8
  } else {
9
    // 长度大于1，获取除第一个数字外的数组的全排列结果
10
    const allSortList = permute(numbs.slice(1));
11
​
12
    // 遍历剩余数字的全排列结果数组
13
    for (let sortIndex = 0; sortIndex < allSortList.length; sortIndex++) {
14
      // 取出不同的全排列结果
15
      const currentSort = allSortList[sortIndex];
16
​
17
      // 将第一个数字插入到不同的位置来生成新的结果，并保存
18
      for (let index = 0; index <= currentSort.length; index++) {
19
        const tempSort = [...currentSort];
20
        tempSort.splice(index, 0, numbs[0]);
21
        result.push(tempSort);
22
      }
23
    }
24
​
25
    // 返回全排列结果数组
26
    return result;
27
  }
28
};
Copied!
复杂度分析：
时间复杂度：O(n3)O(n^3)O(n3)
 时间复杂度由全排列函数  permute 提供。单个全排列函数中存在两层循环嵌套，因此单次调用的时间复杂度为 O(n2)O(n^2)O(n2)
  当 numbs 长度为 nnn
 到 2 时调用全排列函数，即调用 (n−2)(n-2)(n−2)
次  n2(n−2)=n3−2n2n^2(n-2) = n^3 - 2n^2n2(n−2)=n3−2n2
; 当 nnn
 趋近于无限大时，nnn
 可以忽略，因此时间复杂度为 O(n3)O(n^3)O(n3)
​
空间复杂度：O(n3)O(n^3)O(n3)
， 在循环体内使用4个变量，空间复杂度为 O(4∗n3)O(4*n^3)O(4∗n3)
 ，当 nnn
 趋近于无限大，忽略系数，即为 O(n3)O(n^3)O(n3)
​
单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例
1
board =
2
[
3
  ['A','B','C','E'],
4
  ['S','F','C','S'],
5
  ['A','D','E','E']
6
]
7
​
8
给定 word = "ABCCED", 返回 `true`.
9
给定 word = "SEE", 返回 `true`.
10
给定 word = "ABCB", 返回 `false`.
Copied!
方法 回溯算法
思路
题目给的要求水平相邻或垂直相邻的单元格，这与回溯的思想非常相似，简单来说，上下左右都去走一遍，发现不符合要求立即返回。
以题目的示例为例子，从 A 开始，放四个方向试探，如果不匹配，立即换方向
详解
1.从起点开始，枚举所有的可能性，递归搜索
2.如果当前字符串匹配，再考虑上下左右 4 个方向，当发现超出边界或者不匹配时，立即结束当前方向的搜索
1
/**
2
 * @param {character[][]} board
3
 * @param {string} word
4
 * @return {boolean}
5
 */
6
const exist = function (board, word) {
7
  const m = board.length;
8
  const n = board[0].length;
9
​
10
  for (let i = 0; i < m; i++) {
11
    for (let j = 0; j < n; j++) {
12
      if (wordSearch(i, j, 0)) {
13
        return true;
14
      }
15
    }
16
  }
17
​
18
  function wordSearch (i, j, k) {
19
    // 超出边界或者不匹配时，返回 false
20
    if (i < 0 || j < 0 || i >= m || j >= n || word[k] !== board[i][j]) {
21
      return false;
22
    }
23
​
24
    // 找到最后一个字符，返回 true，为递归的终止条件
25
    if (k === word.length - 1) {
26
      return true;
27
    }
28
​
29
    // 先占位
30
    const temp = board[i][j];
31
    board[i][j] = '-';
32
    // 往四个方向递归搜索，有一个方向匹配就可以了
33
    const res = wordSearch(i + 1, j, k + 1) ||
34
      wordSearch(i - 1, j, k + 1) ||
35
      wordSearch(i, j + 1, k + 1) ||
36
      wordSearch(i, j - 1, k + 1);
37
​
38
    // 四个方向搜索完了释放
39
    board[i][j] = temp;
40
​
41
    return res;
42
  }
43
​
44
  return false;
45
};
Copied!
复杂度分析
时间复杂度： O((m∗n)2)O((m*n)^2)O((m∗n)2)
 
​mmm
 和 nnn
 分别是矩阵的行数和列数。 每个递归函数 wordSearch 的调用次数为 m∗nm * nm∗n
，并且调用了4个递归函数，复杂度为 O(4∗m∗n)O(4 * m * n)O(4∗m∗n)
 在 for 循环下，时间复杂度为 O(m∗n)O(m * n)O(m∗n)
。 因此总的时间复杂度为 O(4(m∗n)2)=O((m∗n)2)O(4 (m * n)^2) = O((m*n)^2)O(4(m∗n)2)=O((m∗n)2)
 
空间复杂度： O(m∗n)O(m*n)O(m∗n)
 
每个递归函数的递归深度为 m∗nm * nm∗n
, 空间复杂度为 O(m∗n)O(m * n)O(m∗n)
，一共调用了4个，因此总的复杂度为 O(4∗m∗n)=O(m∗n)O(4 * m *  n) = O(m * n)O(4∗m∗n)=O(m∗n)
 