我接受了软件开发人员职位的采访。那是电话采访。被问到了，这整天困扰着我
面试官让我想出一种在单词搜索网格上查找单词的一般方法。为简单起见，无需担心内存限制或在网格上对角搜索（从左到右，从上到下）。
我能想到的最好的办法是在网格程序启动时创建一个哈希图（每次调用单词search之前……让它创建一个character => row ，col索引。这样，您可以在O（1）时间内执行初始扫描。然后从那里基本上从左到右或从上到下扫描。
我从他那里得到的印象是，有一个更好的解决方案，而我还没有。解决此类问题最快的算法是什么？
如果内存不是问题，并且我可以预处理数据，那么我会：
[当给出要搜索的单词时，我将使用标准搜索算法（KMP，Boyer-Moore等）：]
这在简单性，内存使用和速度之间取得了很好的平衡。实际上，这非常简单，因为您实际上不需要实现搜索算法。只需使用运行时库提供的任何内容。
当然，您可以轻松地修改标准搜索算法，将二维网格视为一维字符串，而无需提前进行实际转换。这比预处理更复杂，并且在搜索中会稍慢一些，但是需要更少的内存。
单次扫描就地完成变得很复杂。但是您可以在一次扫描中轻松地进行水平搜索（即从左到右和从右到左）。垂直搜索只需一次扫描。您只需一次搜索两个不同的字符串：单词和单词的反向版本。
如果预处理数据不计入时间，则可以准备一个向量数组，其中包含每个字母的位置。因此，考虑到第一个字母，您将直接转到出现该字母的位置，然后检查4个（或8个）方向以查找其余字母。
在另一个答案的注释中，@ deAtog似乎建议使用数组查找第一个和最后一个字母的位置。但是，即使对于中等大小的网格，每个字母也可能会出现4次以上，因此仅检查4个方向可能会更快。
您可以将数组的构想扩展到一个数字数组（2个字母的组合）。语法图包含语法图的位置和方向现在，给定单词的前2个字母，您将直接转到这些字母的位置和方向。对于单字母单词，您只需检查所有以字母开头的字母。我认为这提供了大小和速度的良好组合。
如果您真的不在乎空间，则可以将数组的构想扩展到一路，以使例如50,000个最受欢迎的单词的位置和方向保持一致。现在，如果您得到该列表中的单词，则可以在找到该单词在一致性中所需的时间内找到它。
但是我认为一致性太高了。将图映射到位置/方向可能是速度和空间的良好折衷。
最后，如果预处理does很重要，而您只想查找一个单词，那么您可以对蛮力方法应用技巧：将网格存储在边框周围，并留有多余的空格。这些包含一个非字母。这样做意味着您不必检查数组边界。如果您超出网格的边缘，则该值将与单词中的任何字母都不匹配，因此您将在此处停止检查。
从网格构建确定性有限状态机是O(rows*columns)。
在最坏的情况下，检查单个单词为O(word length)。
我想说的是他要您推动澄清。如果您要搜索words，那么我同意您的方法。如果您要搜索单个单词，则线性搜索第一个字母，然后在各个方向搜索其余单词会更快。