谷歌店面面经

一个大的dictionary,就是给了一堆 word,另外给一个target word,找跟target word差别最小的前三个word。
比如 dictionary 是:at, cat,mat,map,kate,kite,set,sad,fat
target word是: cat
返回 cat(差0),mat(差1),fat(差1)

followup是前k个,不是3个

必须跟target word长度一样
这题的关键是三个的时候怎么做

先扫一遍dict 用hashmap存单词 和不同的字符个数。
再用一个list存单词。或者创建一个类存单词和不同字符数 再加进list里。
然后对这个list做quickselect
我觉得这个前k个应该是考quickselect

要注意跟使用heap的tradeoff

但你还是在说followup

正题是前三个

我想问一下这个词之间的差别怎么算? 例如 hateateate, target word是 cat,它怎么算差别?因为有重复的pattern, 那它只算一次么?hateateate (差4 还是 差8)?

逐个计算edit distance,然后以此建立最小堆?