最快的方法是找到一个单词的编辑距离,给出一个百万字的列表

Question

我有一个超过一百万字的文件,每行一个字.我正在尝试编写代码,如果给我一个单词,我需要找出文件中是否存在该单词.这里的问题是,每个单词都必须经过26^(word.length()-1)多次检查.因此,浏览文件中的每个单词都不是一个好的解决方案.我尝试在网上找到算法,但还没有找到任何明显的答案.

编辑 我考虑过a HashMap和Trie.这里的实际问题是说我有这个词abc.现在,我的任务是在单词中添加,删除或替换一个字母abc来创建单词X,然后检查X是否在文件中.因此,对于哪种解决方案可能是更好的方法感到困惑.

Answer 1

您可以根据文件中的单词构建一个trie.这将使用比Hashset少得多的内存,并允许您检查O中单词的存在(单词中的字符数).如果内存不是问题,那么Hashset当然会这样做(因为它的内置也少得多).