2023 Amazon intern VO 跪

为什么不先把prefix 加到trie里面，然后遍历word list，check是否contain 这个prefix，如果是的话就加到list里？

Trie的话time complexity会差不多？空间肯定多点。build trie = O(len(list) * len(longest word)). 直接prefix和每个单词比一共O(len(list) * len(prefix))。len(prefix) 一般比len(longest word)更加短。如果有很多prefix的话trie更好。

匿名用户 发表于 2022-09-01 19:22:37
估计让实现KMP算法

kmp不是在目标串里寻找子串吗 都prefix了还需要kmp干什么…还是说有什么奇技淫巧

楼主收到拒信了吗？没有结果前都不一定啊