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

实现数组的全排列

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例

给定 numbs = [1,2,3];
返回
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

方法一 回溯法

思路

回溯法通常是构造一颗生成树,生成树排列法的核心思想为: 遍历需要全排列的数组,不断选择元素,将不同的数字生成一颗树,如果数组中待选择的结点数为 0,则完成一种全排列。

详解

从上面的思路中,我们可以抽象出全排列函数的步骤:

1. 遍历需要全排列的数组,取出不同位置的数字,创建以对应位置数字为根节点的树。
2. 遍历剩下的数组,选出一个数字,将该数字挂在生成的树上。
3. 重复第二步操作直到剩余数字数组的长度为0,表明完成了全排列,将生成的树存入排序结果数组中。

举个例子:输入数组为 [1, 2, 3],首先选择 1 为根节点,剩余数组为 [2, 3],继续选择 2 作为下一个结点,剩余数组为 [ 3 ],那么选择 3 为最后一个结点,那么 [1, 2, 3] 组成一种全排列情况。 我们回溯到第二步剩余数组,选择 3 为第二个结点,那么剩余数组为 [ 2 ],选择后完成 [1, 3, 2] 这种全排列情况。后续依次固定 2,3 为根结点,列出所有可能。

从上述内容中可以看出,生成初始树后就是一个 截取数组 -> 设置节点,继续 截取节点 -> 设置节点 的递归过程了。那么我们是否可以将第一步的操作合并到我们的递归函数中呢?

既然我们递归的操作是截取数字,并将对应的数字与目标树结合。那么我们可以将第一步看为数字和空树结合。

那么我们递归函数的参数就确定为:

  • 剩余的数组

  • 现有的顺序树

递归函数的逻辑也可以收敛为:

  1. 遍历需要全排列的数组,将不同位置的数字与目前树结合起来

  2. 重复该操作直到需要全排列的数组长度为 0,即表明完成了全排列。

代码

const permute = function (numbs) {
const allSortResult = []; // 设置结果数组
function recursion (restArr, tempResult) {
for (let index = 0; index < restArr.length; index++) {
// 获取不同位置的数字
const insertNumb = restArr[index];
// 将不同位置的数字与现有的顺序树相结合
const nextTempResult = [...tempResult, insertNumb];
/**
* 判断传入的数组长度
* 大于1:
* 继续递归,参数分别为:
* 1. 除去当前数字外的数组
* 2. 新生成的树
* 等于1(不会出现小于1的情况):
* 表明已经结合到了最后一个节点,将生成的顺序树推送到结果数组中
*/
if (restArr.length > 1) {
recursion(
restArr.filter(resetNumb => resetNumb !== insertNumb),
nextTempResult
);
} else {
allSortResult.push(nextTempResult);
}
}
}
// 调用递归方法,开始生成顺序树
recursion(numbs, []);
// 返回全排列结果
return allSortResult;
};

复杂度分析

  • 时间复杂度:O(n2)O(n^2)

  • 空间复杂度:O(n2)O(n^2)

方法二 插值排序法

思路

插值排列法的核心思想为: 遍历需要全排列的数组,将不同位置的数字抽离出来,插入到剩余数组的不同位置,即可得到该数字与另一个数组的全排列结果。 将一个固定的数字,插入到另一个数组的全排列结果的不同位置, 遍历需要全排列的数组,将不同的数字连接到不同的树上 继续全排列剩下的数组与生成的树,当剩余数组长度为0时,表明完成了全排列。

详解

从上面的思路中,我们可以抽象出插值排序全排列方法的具体实现:

首先处理特殊情况。如果传入排列的数组长度为1,直接返回该数组。否则进行下面的全排列方法

1. 截取传入数组的第 1 位数字,将剩余数组传入获取全排列方法函数,获取剩余数字的全排列结果
2. 遍历剩余数字的全排列结果数组并取出各个结果
3. 使用循环将截取的数字插入到不同结果(数组)的不同位置,生成新的全排列结果并保存
4. 返回全排列结果数组

代码

const permute = function (numbs) {
// 设定保存结果变量
const result = [];
// 如果长度为1,只有一种排列,直接返回
if (numbs.length === 1) {
return [numbs];
} else {
// 长度大于1,获取除第一个数字外的数组的全排列结果
const allSortList = permute(numbs.slice(1));
// 遍历剩余数字的全排列结果数组
for (let sortIndex = 0; sortIndex < allSortList.length; sortIndex++) {
// 取出不同的全排列结果
const currentSort = allSortList[sortIndex];
// 将第一个数字插入到不同的位置来生成新的结果,并保存
for (let index = 0; index <= currentSort.length; index++) {
const tempSort = [...currentSort];
tempSort.splice(index, 0, numbs[0]);
result.push(tempSort);
}
}
// 返回全排列结果数组
return result;
}
};

复杂度分析:

  • 时间复杂度: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)

单词搜索

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例

board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 `true`.
给定 word = "SEE", 返回 `true`.
给定 word = "ABCB", 返回 `false`.

方法 回溯算法

思路

题目给的要求水平相邻或垂直相邻的单元格,这与回溯的思想非常相似,简单来说,上下左右都去走一遍,发现不符合要求立即返回。

以题目的示例为例子,从 A 开始,放四个方向试探,如果不匹配,立即换方向

详解

  1. 从起点开始,枚举所有的可能性,递归搜索

  2. 如果当前字符串匹配,再考虑上下左右 4 个方向,当发现超出边界或者不匹配时,立即结束当前方向的搜索

/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
const exist = function (board, word) {
const m = board.length;
const n = board[0].length;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (wordSearch(i, j, 0)) {
return true;
}
}
}
function wordSearch (i, j, k) {
// 超出边界或者不匹配时,返回 false
if (i < 0 || j < 0 || i >= m || j >= n || word[k] !== board[i][j]) {
return false;
}
// 找到最后一个字符,返回 true,为递归的终止条件
if (k === word.length - 1) {
return true;
}
// 先占位
const temp = board[i][j];
board[i][j] = '-';
// 往四个方向递归搜索,有一个方向匹配就可以了
const res = wordSearch(i + 1, j, k + 1) ||
wordSearch(i - 1, j, k + 1) ||
wordSearch(i, j + 1, k + 1) ||
wordSearch(i, j - 1, k + 1);
// 四个方向搜索完了释放
board[i][j] = temp;
return res;
}
return false;
};

复杂度分析

  • 时间复杂度: O((mn)2)O((m*n)^2)

    mmnn 分别是矩阵的行数和列数。 每个递归函数 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)