谷歌新鲜店面面经

预处理放入所有可能替换的string也会有O(str.length() * number of strings) 的时间复杂度啊， 不可能O(1)

O(1)就是Trie。
准确地说，是O(strlen）。任何search都需要至少O(strlen）。

LebronRice 发表于 2018-11-2 14:58
预处理放入所有可能替换的string也会有O(str.length() * number of strings) 的时间复杂度啊， 不可能O(1)

只优化search function， zszs

hername 发表于 2018-11-2 17:18
O(1)就是Trie。
准确地说，是O(strlen）。任何search都需要至少O(strlen）。

这道题我之前准备面经的时候看过，trie的方法不是很好，而且复杂度也高。请问小伙伴是否有好的TRIE解法link？

我觉得对于follow up，如果建立字典的时候，把所有能替换一个字符形成的单词和原来的单词全都放进一个set里，search的时候检查set存不存在那个单词就是O（1）了吧。只是这样建立字典的时间复杂的就很高。总体来说整个类的时间复杂度反而会更高。

然后676和这个好像不太一样，676要求必须且只能替换一个字符。这个面试题可以不替换的吧？

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

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

用 # 替换字符。如 good -> #ood, g#od 等，作为 key
value 是一个list, 存所有能形成 key  的 original words

search word:  逐个用#替换字符作为key，如果存在key，就看对应的list, 如果 len(list) > 1 或者 list[0] != word, return True