2023 Amazon intern VO 跪

2023 Summer intern 昨天VO, 问了个 已知 prefix 返回列表所有满足的单词，

您好！
本帖隐藏的内容需要积分高于 29 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 29 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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-9-1 00:07
Trie Tree加dfs呗…还能有什么更好的算法吗…

这样的话 就是列表单词长度O(N) 复杂度了吧，如果列表所有单词都满足prefix

namistte 发表于 2022-9-1 21:39
其实可以每个node存当前prefix的所有单词，就是空间会用得多一点。

别勾起我回忆了，我就是那么写的。。。。

Trie Tree加dfs呗…还能有什么更好的算法吗…

有结果吗现在

这不就是标准的trie吗？

匿名用户 发表于 2022-9-1 18:48
这不就是标准的trie吗？

这个找符合prefix的单词，直接遍历一遍不就可以了吗

小亩_b6f7ef1 发表于 2022-9-1 15:23
这个找符合prefix的单词，直接遍历一遍不就可以了吗

嗯嗯，for char in prefix

估计让实现KMP算法

其实可以每个node存当前prefix的所有单词，就是空间会用得多一点。