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

实现数组的全排列

给定一个没有重复数字的序列,返回其所有可能的全排列。
示例
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. 1.
    遍历需要全排列的数组,将不同位置的数字与目前树结合起来
  2. 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(n^2)

方法二 插值排序法

思路
插值排列法的核心思想为: 遍历需要全排列的数组,将不同位置的数字抽离出来,插入到剩余数组的不同位置,即可得到该数字与另一个数组的全排列结果。 将一个固定的数字,插入到另一个数组的全排列结果的不同位置, 遍历需要全排列的数组,将不同的数字连接到不同的树上 继续全排列剩下的数组与生成的树,当剩余数组长度为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)
    时间复杂度由全排列函数 permute 提供。单个全排列函数中存在两层循环嵌套,因此单次调用的时间复杂度为
    O(n2)O(n^2)
    当 numbs 长度为
    nn
    到 2 时调用全排列函数,即调用
    (n2)(n-2)
    n2(n2)=n32n2n^2(n-2) = n^3 - 2n^2
    ; 当
    nn
    趋近于无限大时,
    nn
    可以忽略,因此时间复杂度为
    O(n3)O(n^3)
  • 空间复杂度:
    O(n3)O(n^3)
    , 在循环体内使用4个变量,空间复杂度为
    O(4n3)O(4*n^3)
    ,当
    nn
    趋近于无限大,忽略系数,即为
    O(n3)O(n^3)

单词搜索

给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例
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. 1.
    从起点开始,枚举所有的可能性,递归搜索
  2. 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((mn)2)O((m*n)^2)
    mm
    nn
    分别是矩阵的行数和列数。 每个递归函数 wordSearch 的调用次数为
    mnm * n
    ,并且调用了4个递归函数,复杂度为
    O(4mn)O(4 * m * n)
    在 for 循环下,时间复杂度为
    O(mn)O(m * n)
    。 因此总的时间复杂度为
    O(4(mn)2)=O((mn)2)O(4 (m * n)^2) = O((m*n)^2)
  • 空间复杂度:
    O(mn)O(m*n)
    每个递归函数的递归深度为
    mnm * n
    , 空间复杂度为
    O(mn)O(m * n)
    ,一共调用了4个,因此总的复杂度为
    O(4mn)=O(mn)O(4 * m * n) = O(m * n)