实现一个单词搜索游戏，给定一个二维网格和一个单词列表，找到单词列表中出现在网格中的所有单词（提示：Trie树 + DFS）。
简介：实现一个单词搜索游戏，给定一个二维网格和一个单词列表，找到单词列表中出现在网格中的所有单词（提示：Trie树 + DFS）。
算法思路
算法思路：
- 本题要求我们查找单词列表中所有在二维网格中出现的单词。由于单词可以出现在网格中的任意位置，因此需要从每个单元格开始遍历整个网格。但是如果直接对每个单元格都进行一次DFS的话时间复杂度会很高
- 有一个优化方法是将所有单词加入到Trie树中。这样我们可以依次从每个单元格开始向四个方向深度优先搜索，并以此检查路径是否与某个单词匹配，实现单词搜索游戏。
下面是C++代码实现，每行注释详细解释其作用：
#include <iostream> #include <vector> #include <string> using namespace std; class Trie { // 定义 Trie 树 public: Trie* children[26]; // 26 个字母 bool isEndOfWord; // 当前节点是否为单词结尾 Trie() { isEndOfWord = false; for (int i = 0; i < 26; i++) children[i] = NULL; } }; class Solution { private: vector<string> res; // 存储结果 public: void insert(Trie* root, string word) { // 将单词插入到 Trie 树中 Trie* node = root; for (char c : word) { if (!node->children[c - 'a']) node->children[c - 'a'] = new Trie(); node = node->children[c - 'a']; } node->isEndOfWord = true; } vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { // WordSearch函数的实现 Trie* root = new Trie(); // 新建 Trie 树 for (string word : words) insert(root, word); // 将单词插入 Trie 树中 int m = board.size(), n = board[0].size(); // 获取矩阵的长和宽 vector<vector<bool>> visited(m, vector<bool>(n, false)); // 存储访问情况 string word; // 当前单词 for (int i = 0; i < m; i++) { // 遍历整个网格，从每个位置开始搜索 for (int j = 0; j < n; j++) { dfs(board, visited, root, word, i, j); // 开始 DFS } } return res; } void dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, Trie* node, string& word, int i, int j) { // DFS函数的实现 if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || visited[i][j]) return; // 如果当前单元格已经被访问或者越过了边界，则退出DFS char c = board[i][j]; // 当前单元格的字母 if (!node->children[c - 'a']) return; // 如果Trie树中不存在以该字母为开头的单词，则退出DFS node = node->children[c - 'a']; // 遍历到Trie树中对应的子节点 word += c; // 将当前字母加入到字符串中 if (node->isEndOfWord) { // 判断当前剪枝是否为一个单词的结尾 res.push_back(word); // 如果是，则将该单词加入结果中 node->isEndOfWord = false; // 防止出现重复单词 } visited[i][j] = true; // 标记当前单元格已经被访问 dfs(board, visited, node, word, i - 1, j); // 向上搜索 dfs(board, visited, node, word, i + 1, j); // 向下搜索 dfs(board, visited, node, word, i, j - 1); // 向左搜索 dfs(board, visited, node, word, i, j + 1); // 向右搜索 visited[i][j] = false; // 恢复当前单元格状态，避免影响其他的 DFS 流程 word.pop_back(); // 将当前字母弹出字符串 } }; int main() { Solution sol; vector<vector<char>> board = {{'o','a','a','n'}, {'e','t','a','e'}, {'i','h','k','r'}, {'i','f','l','v'}}; vector<string> words = {"oath","pea","eat","rain"}; // 单词列表 vector<string> result = sol.findWords(board, words); // WordSearch函数调用 for (string s : result) cout << s << " "; // 输出结果 return 0; }
需要说明的是，在程序中我们定义一个 Trie 树来储存单词列表。首先将所有的单词插入到 Trie 树中，然后遍历整个网格，在每个位置开始 DFS 流程，向四周不断扩展字符串，如果该字符串在 Trie 树中查询到，则将其加入结果的列表中。
同时，在进行 DFS 遍历时还需要考虑到边界的有效性和已经访问过的单元格不能重复访问等问题。为了满足这些条件，我们使用一个 visited 数组来记录每个坐标是否已经被访问过。
最后根据题目要求，返回所有找到的字符串作为结果即可。
- Java版本
class Trie { // 定义 Trie 树 Trie[] children; // 26 个字母 boolean isEndOfWord; // 当前节点是否为单词结尾 public Trie() { isEndOfWord = false; children = new Trie[26]; } } class Solution { List<String> res; // 存储结果 public void insert(Trie root, String word) { // 将单词插入到 Trie 树中 Trie node = root; for (char c : word.toCharArray()) { if (node.children[c - 'a'] == null) node.children[c - 'a'] = new Trie(); node = node.children[c - 'a']; } node.isEndOfWord = true; } public List<String> findWords(char[][] board, String[] words) { // WordSearch函数的实现 Trie root = new Trie(); // 新建 Trie 树 for (String word : words) insert(root, word); // 将单词插入 Trie 树中 int m = board.length, n = board[0].length; // 获取矩阵的长和宽 boolean[][] visited = new boolean[m][n]; // 存储每个位置的访问情况 res = new ArrayList<>(); // 初始化结果数组 StringBuilder word = new StringBuilder(); // 存储当前单词 for (int i = 0; i < m; i++) { // 遍历整个网格，从每个位置开始搜索 for (int j = 0; j < n; j++) { dfs(board, visited, root, word, i, j); // 开始 DFS } } return res; } public void dfs(char[][] board, boolean[][] visited, Trie node, StringBuilder word, int i, int j) { // DFS函数的实现 if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j]) return; // 如果当前单元格已经被访问或者越过了边界，则退出DFS char c = board[i][j]; // 当前单元格的字母 if (node.children[c - 'a'] == null) return; // 如果Trie树中不存在以该字母为开头的单词，则退出DFS node = node.children[c - 'a']; // 遍历到Trie树中对应的子节点 word.append(c); // 将当前字母加入到字符串中 if (node.isEndOfWord) { // 判断当前剪枝是否为一个单词的结尾 res.add(word.toString()); // 如果是，则将该单词加入结果中 node.isEndOfWord = false; // 防止出现重复单词 } visited[i][j] = true; // 标记当前单元格已经被访问 dfs(board, visited, node, word, i - 1, j); // 向上搜索 dfs(board, visited, node, word, i + 1, j); // 向下搜索 dfs(board, visited, node, word, i, j - 1); // 向左搜索 dfs(board, visited, node, word, i, j + 1); // 向右搜索 visited[i][j] = false; // 恢复当前单元格状态，避免影响其他的 DFS 流程 word.deleteCharAt(word.length() - 1); // 将当前字母从字符串中删除 } } public class Main { public static void main(String[] args) { Solution sol = new Solution(); char[][] board = {{'o','a','a','n'}, {'e','t','a','e'}, {'i','h','k','r'}, {'i','f','l','v'}}; String[] words = {"oath","pea","eat","rain"}; // 单词列表 List<String> result = sol.findWords(board, words); // WordSearch函数的调用 System.out.println(result); // 输出结果 } }
