Word Search II单词搜索问题中为何选择使用Trie数据结构？

Word Search II 规则：给定m×n字符网格与字符串列表words，要求返回网格中存在的所有单词。单词需由顺序相邻的单元格字母构成，相邻指水平或垂直方向相邻，单个单词构造中同一单元格仅可使用一次。

核心原因是Trie能大幅降低搜索的时间开销，相比暴力解法有本质的性能提升： #

• 前缀匹配剪枝，避免重复搜索
  暴力解法通常是对每个单词单独在网格中跑DFS搜索，如果单词列表有大量前缀重合的单词（比如app、apple、apply），会重复走大量相同的DFS路径。而把所有待搜索单词预先存入Trie后，我们只需要对网格跑一次全局DFS，每走一步只需要检查当前字符是否存在于Trie当前节点的子节点中，不存在直接剪枝，所有前缀重合的单词可以共享同一段路径的匹配结果，不需要为每个单词单独启动搜索。
• O(1)判断单词匹配完成
  我们可以在Trie的节点上直接标记「是否为单词结尾」，甚至直接存储对应完整单词。当DFS走到某一字符时，如果对应Trie节点标记为单词结尾，就可以直接将该单词加入结果集，不需要额外做字符串比对或者哈希查找。
• 天然支持结果去重
  匹配到某一单词后，可以直接删除Trie中该单词的结尾标记，后续即使网格中有其他路径能拼出相同单词，也不会重复加入结果集，不需要额外维护哈希表做去重，简化逻辑同时节省空间。

时间复杂度对比 #

假设单词总字符数为S，网格大小为m×n，单词最大长度为L：

• 暴力逐词搜索的时间复杂度为：O(words.length * m * n * 4^L)，性能随单词数量增长线性下降，单词量大时完全不可用。
• Trie方案的时间复杂度为：O(S + m * n * 4^L)，构建Trie的开销仅和单词总字符数相关，后续搜索开销完全不随单词数量增长而提升，前缀重合度越高，性能优势越明显。

内容的提问来源于stack exchange，提问作者Vik。