寻找二维网格中的单词

“单词搜索 II”是一个关于算法问题的讨论，主要涉及如何在给定的二维字符网格中寻找字典中列出的所有单词。这个问题要求单词必须按照字母顺序，通过相邻的单元格构建，并且不能重复使用同一单元格内的字母。 题目描述了一个二维字符网格board和一个单词列表words，目标是找出所有同时存在于grid和words中的单词。单词必须水平或垂直相邻，不能斜向连接，并且每个单词的字母不能重复使用同一单元格。提供的示例展示了如何在给定的grid中找到符合要求的单词。 提示信息明确了输入参数的限制，例如grid的行数和列数、单词列表的长度以及单词的长度范围，所有单词由小写英文字母组成，且彼此不同。 参考答案部分给出了一种可能的解决方案，使用了 Trie 数据结构来辅助搜索。TrieNode 类包含一个字符串成员变量 word 和一个大小为 26 的 vector，用于存储子节点，表示26个英文字母。Solution 类则包含了对问题的主要处理方法 findWords，它首先获取grid的尺寸，然后在内部实现查找逻辑。 在 findWords 方法中，首先构建一个 Trie 树，将所有单词插入。接着，对grid的每个单元格进行深度优先搜索（DFS），在搜索过程中，每次尝试构造一个单词并从 Trie 树中查找是否存在。如果找到一个完整的单词，就将其添加到结果列表 res 中。DFS 过程中，需要维护当前路径的字符串，并在回溯时清除路径。 这个算法的关键在于利用 Trie 数据结构高效地查找单词，同时结合深度优先搜索遍历grid。在实际实现中，还需要考虑边界条件和优化搜索效率，例如避免回溯到已经访问过的单元格，以及在 Trie 中提前剪枝等策略。 “单词搜索 II”是一个典型的组合问题，它结合了数据结构（Trie）和图遍历（DFS）算法，对于提升编程能力和解决实际问题的能力有很大帮助。