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

Question

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

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

我能想到的最好办法是在网格程序启动时创建一个散列映射(在每次调用单词搜索之前)...让它创建一个散列映射 character = > 行、列索引。这样您就可以在 O(1) 时间内执行初始扫描。然后从那里基本上从左到右或从上到下扫描。

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

Answer 1

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

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

当给出要搜索的词时，我会使用标准搜索算法(KMP、Boyer-Moore 等)来:

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

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

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

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