我接受了一个软件开发人员职位的面试。那是一次电话采访。被问到这个问题，它一直困扰着我一整天
面试官让我想出一个在单词搜索网格上查找单词的通用方法。为了简单起见，无需担心内存限制或在网格上对角搜索（从左到右，从上到下）。
我能想到的最好的办法是在网格程序启动时创建一个哈希图（在每次调用单词搜索之前）。。。让它创建一个字符=>行、col索引的哈希映射。这样，您可以在O（1）时间内执行初始扫描。然后从那里基本上从左到右或从上到下扫描。
我从他那里得到的印象是有更好的解决方案，而我还没有做到。解决这样一个问题最快的算法是什么？
如果内存不是问题，并且我可以预处理数据，那么我会：
- 按行主顺序制作网格的字符串表示形式。这是用于水平搜索的
- 按列主顺序制作网格的字符串表示，用于垂直搜索
当给定一个单词进行搜索时，我会使用标准搜索算法（KMP、Boyer-Moore等）来：
- 在行主字符串中搜索单词
- 反转单词并在行中搜索主字符串
- 在列主字符串中搜索单词
- 反转单词并在列主字符串中搜索
这在简单性、内存使用率和速度之间取得了很好的平衡。事实上，它非常简单，因为您不需要真正实现搜索算法。只需使用运行库提供的任何内容。
当然，您可以很容易地修改标准搜索算法，将二维网格视为一维字符串，而无需提前进行转换。这比预处理更复杂，搜索速度也会稍慢，但需要更少的内存。
只需一次扫描就可以完成这项工作，这会变得很复杂。但你可以在一次扫描中很容易地进行水平搜索（即从左到右和从右到左）。并且在一次扫描中进行垂直搜索。你只需要在一次遍历中搜索两个不同的字符串：单词和单词的反转版本。
如果预处理数据不计入时间，那么您可以准备一个包含每个字母位置的向量数组。因此，给定第一个字母，你可以直接找到它出现的位置，然后检查其余字母的4（或8）个方向。
在对另一个答案的评论中，@deAtog似乎建议使用数组来查找第一个和最后一个字母的位置。但即使是中等大小的网格，每个字母的出现次数也可能超过4次，因此只检查4个方向可能会更快。
您可以将数组思想扩展到有向图数组（2个字母的组合）。有向图包含有向图的位置和方向现在给定单词的前两个字母，你可以直接找到这些字母的位置和指向。对于单字母单词，您只需检查以字母开头的所有离题。我认为这提供了一个很好的组合大小和速度。
如果你真的不在乎空间，你可以将数组的想法一直扩展到创建最流行的50000个单词的位置和方向的一致性。现在，如果你得到了该列表中的一个单词，你可以在找到该单词所需的时间内找到它。
但我认为这种一致性有些过头了。将有向图映射到位置/方向可能是速度和空间的一个很好的折衷方案。
最后，如果预处理确实很重要，并且您只需要查找一个单词，那么您可以对蛮力方法应用一个技巧：在边界周围存储带有额外空间的网格。这些包含一个非字母。这样做意味着您永远不必检查数组边界。如果你偏离了网格的边缘，那里的值与单词中的任何字母都不匹配，所以你会停止检查。
我想说他希望你推动澄清。如果您正在搜索单词，那么我同意您的方法。如果你在搜索一个单词，那么线性搜索第一个字母，然后在每个方向搜索单词的其余部分会更快。