在单词搜索网格上查找单词的最快算法

Question

我接受了软件开发人员职位的面试。那是电话面试。被问到这个问题，它一直困扰着我一整天

面试官让我想出一个在单词搜索网格上查找单词的通用方法。为简单起见，无需担心内存限制或在网格上对角搜索（从左到右，从上到下）。

我能想到的最好方法是在网格程序启动时创建一个哈希映射（在每次调用单词搜索之前）......让它创建一个字符=> row,col indices的哈希映射。这样你就可以在 O(1) 时间内执行初始扫描。然后从那里基本上从左到右或从上到下扫描。

我从他那里得到的印象是有一个更好的解决方案，而我还没有。解决此类问题的最快算法是什么？

Answer 1

如果内存不是问题并且我可以预处理数据，那么我会：

1. 按行优先顺序制作网格的字符串表示形式。这是为了水平搜索。
2. 按列优先顺序制作网格的字符串表示形式，以便垂直搜索。

当给定一个要搜索的单词时，我会使用标准搜索算法（KMP、Boyer-Moore 等）来：

1. 在行主字符串中搜索单词。
2. 反转单词并在行优先字符串中搜索。
3. 在列主字符串中搜索单词。
4. 反转单词并在列主字符串中搜索。

这在简单性、内存使用和速度之间提供了良好的平衡。事实上，它非常简单，因为您实际上不需要实现搜索算法。只需使用运行时库提供的任何内容即可。

当然，您可以轻松修改标准搜索算法，将二维网格视为一维字符串，而无需提前实际进行转换。这比预处理更复杂，搜索速度稍慢，但需要的内存更少。

通过一次扫描就地完成它会变得很复杂。但是您可以在一次扫描中轻松地进行水平搜索（即从左到右和从右到左）。并在一次扫描中进行垂直搜索。您只需在一次传递中搜索两个不同的字符串：单词和单词的反向版本。