学习记录：js算法（六十二）：单词搜索 II
单词搜索 II
给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。
单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
图一：
图二：
示例 1：图一
输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]
示例 2：图二
输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]
思路一
var findWords = function(board, words) {
const root = {};
const result = [];
// 构建字典树
words.forEach(word => {
let node = root;
for (const char of word) {
if (!node[char]) {
node[char] = {};
}
node = node[char];
}
node.end = word;
});
// DFS 搜索函数
const dfs = (node, i, j, str) => {
const char = board[i][j];
if (char === '#' || !node[char]) {
return;
}
str += char;
node = node[char];
if (node.end) {
result.push(node.end);
delete node.end; // 防止重复添加
}
// 四个方向搜索
const directions = [[0,1], [0,-1], [1,0], [-1,0]];
directions.forEach(([dx, dy]) => {
const ni = i + dx;
const nj = j + dy;
if (ni >= 0 && ni < board.length && nj >= 0 && nj < board[0].length) {
board[i][j] = '#'; // 标记为已访问
dfs(node, ni, nj, str);
board[i][j] = char; // 恢复原始状态
}
});
};
// 遍历整个板子
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
dfs(root, i, j, '');
}
}
return result;
};
讲解
这个问题通常被称为“单词搜索”或“Boggle”游戏问题的扩展版本，其中目标是找出所有可能的单词。
- 构建字典树 (Trie):
○ 字典树是一种高效的数据结构，用于存储字符串集合。它允许我们快速检查一个单词是否存在于集合中，以及在搜索过程中逐步检查部分前缀是否有效。
○ 对于给定的单词列表 words，遍历每一个单词，并将其添加到字典树中。在字典树的节点上，我们可以标记单词的结束点，这样在搜索过程中可以快速识别出完整的单词。- 深度优先搜索 (DFS):
○ 对于二维网格上的每一个单元格，我们执行深度优先搜索来探索所有可能的方向（上、下、左、右），同时构建一个路径字符串。
○ 如果在字典树中找到一个完整的单词，则将其添加到结果列表中，并从字典树中删除该单词的结束标记，以避免重复计算相同的单词。
○ 在搜索过程中，为了避免重复访问同一个单元格，我们将访问过的单元格标记为特殊字符（如 #），并在搜索完该路径后恢复原状。- 遍历和搜索:
○ 遍历整个二维网格，从每个单元格开始执行深度优先搜索，直到找到所有的单词为止。
思路二
function findWords(board, words) {
const result = new Set(); // 使用 Set 来存储结果，避免重复
const trie = buildTrie(words); // 构建字典树
const rows = board.length;
const cols = board[0].length;
for (let row = 0; row < rows; row++) {
for (let col = 0; col < cols; col++) {
dfs(board, row, col, trie, "", result);
}
}
return Array.from(result); // 将 Set 转换为数组返回
}
function buildTrie(words) {
const root = {};
for (const word of words) {
let node = root;
for (const char of word) {
if (!node[char]) {
node[char] = {};
}
node = node[char];
}
node.isEnd = true; // 标记单词的结束
}
return root;
}
function dfs(board, row, col, trie, path, result) {
const char = board[row][col];
if (!trie[char]) return; // 如果当前字符不在字典树中，返回
path += char; // 更新路径
trie = trie[char]; // 移动到下一个节点
if (trie.isEnd) {
result.add(path); // 找到一个单词，添加到结果中
}
// 标记当前单元格为已访问
const temp = board[row][col];
board[row][col] = '#'; // 使用特殊字符标记已访问
// 进行 DFS 搜索相邻的单元格
const directions = [
[0, 1], // 右
[1, 0], // 下
[0, -1], // 左
[-1, 0] // 上
];
for (const [dx, dy] of directions) {
const newRow = row + dx;
const newCol = col + dy;
if (newRow >= 0 && newRow < board.length && newCol >= 0 && newCol < board[0].length && board[newRow][newCol] !== '#') {
dfs(board, newRow, newCol, trie, path, result);
}
}
// 恢复当前单元格的状态
board[row][col] = temp;
}
讲解
- 构建字典树（Trie）：buildTrie 函数用于构建一个字典树，以便快速查找单词。
- 深度优先搜索（DFS）：
- dfs 函数用于从当前单元格开始进行深度优先搜索，查找可能的单词。
- 使用一个 path 字符串来存储当前路径的字符。
- 使用一个 result 集合来存储找到的单词。
- 标记已访问的单元格：在 DFS 搜索过程中，将已访问的单元格标记为 ‘#’，以避免重复使用。
- 方向数组：使用一个方向数组来表示四个可能的移动方向（上、下、左、右）
- 返回结果：最后，将结果集合转换为数组并返回。
原文地址：https://blog.csdn.net/weixin_48677331/article/details/142869306
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！