gpt4 book ai didi

不同方向搜索网格的算法

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

今天一位同事向我提出了一个问题。给定一个字符网格和一个单词列表,我们必须在水平、垂直和对角线上找到该单词在网格中的每一次出现。

我们提出的解决方案行之有效,但我很想看看其他人的想法如何。

最佳答案

将列表中的每个单词插入 trie 中, 或 hash table或任何字典。

现在,对于网格中的每个位置,水平、垂直和对角线移动,看看是否在字典中找到匹配项。这应该给你 O(N^3) 最坏情况的复杂性,其中 N 是网格的大小。否则它是 O(N^2*averageWordLength) 我想。

关于不同方向搜索网格的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3247029/

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