抖音seo关键词优化怎么做_全国疫情风险等级查询_谷歌浏览器下载视频_网页制作教程

给定一个 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"]
输出：[]

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] 是一个小写英文字母
• 1 <= words.length <= 3 * 104
• 1 <= words[i].length <= 10
• words[i] 由小写英文字母组成
• words 中的所有字符串互不相同

解题分析

问题性质定义

• 输入：

  1. 一个二维字符网格 board，大小为 m×nm \times n。
  2. 一个单词列表 words。

• 输出：所有可以在网格上找到的单词列表。

• 限制条件：

  1. 单词必须按相邻单元格顺序构成，单元格可以水平或垂直相邻。
  2. 同一单元格内的字母不能重复使用。
  3. 单词列表中的单词互不相同。

• 边界条件：

  1. 空单词列表 words 或空字符网格 board。
  2. 网格很大 m,n≤12m, n \leq 12，单词列表很长 ∣words∣≤3×10^4，需要设计高效算法。
  3. 单词可能部分匹配（前缀匹配），但需要完整匹配才能算找到。

---

解决思路

1. 算法设计：

   • 前缀树 (Trie)：构建 Trie 存储单词列表以高效地支持前缀匹配，避免无效搜索。
   • 深度优先搜索 (DFS)：从每个网格单元格出发，尝试通过 DFS 查找单词，同时避免重复访问。
   • 剪枝优化：
     • 如果当前路径不匹配任何 Trie 前缀，立即停止搜索。
     • 使用标志位标记访问过的单元格。

2. 时间复杂度分析：

   • 构建 Trie：O(L)，其中 L 是 words 中所有单词长度总和。
   • 搜索：对于每个单元格，最差情况下搜索整棵 Trie，时间复杂度为 O(m×n×4k)，其中 k 是单词的最大长度。
   • 总复杂度：结合 Trie 的剪枝优化，实际效率远优于暴力搜索。

3. 空间复杂度：

   • Trie 的空间复杂度为 O(L)。
   • 递归栈深度为单词的最大长度 O(k)。
4. C++ 实现

// Trie 节点定义
struct TrieNode {unordered_map<char, TrieNode*> children;string word = "";  // 保存单词末尾
};// 构建 Trie
class Trie {
public:TrieNode* root;Trie() {root = new TrieNode();}void insert(const string& word) {TrieNode* node = root;for (char c : word) {if (!node->children.count(c)) {node->children[c] = new TrieNode();}node = node->children[c];}node->word = word;  // 在单词结尾保存整个单词}
};class Solution {
public:vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {vector<string> result;Trie trie;// 1. 将所有单词插入 Triefor (const string& word : words) {trie.insert(word);}// 2. 遍历网格，进行深度优先搜索int m = board.size(), n = board[0].size();for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {dfs(board, i, j, trie.root, result);}}return result;}private:void dfs(vector<vector<char>>& board, int i, int j, TrieNode* node, vector<string>& result) {char c = board[i][j];// 剪枝：超出边界或当前字符不在 Trie 中if (c == '#' || !node->children.count(c)) {return;}node = node->children[c];// 如果找到单词，加入结果集if (!node->word.empty()) {result.push_back(node->word);node->word = "";  // 避免重复添加}// 标记当前单元格为已访问board[i][j] = '#';// 递归搜索四个方向int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};for (auto& dir : directions) {int x = i + dir[0], y = j + dir[1];if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size()) {dfs(board, x, y, node, result);}}// 恢复当前单元格board[i][j] = c;// 优化：如果当前 Trie 节点无子节点，删除它if (node->children.empty()) {node = nullptr;}}
};

代码详细解释

1. Trie 的构建：

   • 使用 Trie 存储单词列表，便于高效的前缀匹配。
   • 每个节点存储其子节点映射和一个 word 字符串，用于标记该节点是否是某个单词的末尾。

2. DFS 搜索：

   • 从网格中每个单元格出发，尝试匹配 Trie 中的单词。
   • 剪枝条件：
     • 当前字符不在 Trie 中。
     • 当前单元格已访问（用 # 标记）。
   • 匹配到单词后，立即加入结果集，并将该单词从 Trie 中删除（防止重复匹配）。
   • 搜索四个方向的邻居单元格。

3. 优化：

   • 标记访问过的单元格，避免重复路径。
   • 当某个 Trie 节点的 children 为空时，提前释放内存。

---

启发与实际应用

启发：

• Trie 结合 DFS 是解决字符串匹配问题的经典方法，特别适合大规模、多前缀的单词匹配场景。
• 剪枝优化和内存管理在搜索问题中至关重要，可以极大提升性能。

实际应用：

• 拼写检查：在输入法、文本编辑器中高效匹配单词。
• 词频分析：在网格状数据中统计出现的关键词。
• 游戏开发：如文字搜索游戏，可以快速匹配玩家找到的单词。

示例场景：

输入法联想：

• 需求：用户输入拼音或字母时，联想出可能的候选词。
• 实现：
  • 使用 Trie 存储所有词典。
  • 用户输入字符时，从 Trie 中按前缀查找所有匹配单词。
  • 联想结果按词频排序，实时显示给用户。