Python 面试题 求解

面试的时候有个题，有一个 list={'kindle', 'sony ps5',...} 如果用户输入一个单词 因为键盘stuck   key，input 例如 kkkkinddle 怎么 去那个list里面找到最佳匹配，有偿求解，求用python解一下 私信我

quincyl 发表于 2020-12-18 14:46:33
红包有偿Python求解，V信 qeenfish

看你怎么定义相似度了。可以找出这个单词和字典里每个单词的的min edit distance（刷题网72），取其中最小的一个就好。

双指针，从尾部往前扫描。

把prefix里重复的char删掉，然后edit distance

楼主可以尝试字典树（trie）

remove duplicate chars and then match

墨明棋妙 发表于 2020-12-20 00:04
remove duplicate chars and then match

我也会这么做，直接用set去重就好了。----- 更新，忽然想到set是unordered，所以不行。。。，但感觉上去重是必要的

字典树请问怎么用？

墨明棋妙 发表于 2020-12-19 08:04:23
remove duplicate chars and then match

这个不一定的吧 万一本身就有重复咋办 比如给的词是 aab 用户输入的是 aaaab 如果去重 就变成了 ab

landmass 发表于 2020-12-29 21:28:25
字典树请问怎么用？

除了指向子节点 再加一个指向本身的指针？