gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:25:36 25 4
gpt4 key购买 nike

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

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

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

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

最佳答案

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

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

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

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

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

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

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

关于algorithm - 在单词搜索网格上查找单词的最快算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26793846/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com