给定一个长度为 l 的正确单词列表和一个长度为 l 的错误单词列表，找出不正确单词列表中与通过交换两个连续字母的正确单词列表。这些词被视为错别字。例如，hte 被认为是 the 的拼写错误，而 het 则不被视为拼写错误。
什么是最省时的算法，可以让我们找到被这个定义视为拼写错误的单词列表？
我被告知列表可以在线性时间内计算，但我无法在线性时间内找到解决方案。我能想到的唯一方法是将一个列表中的所有字母与另一个列表中的所有字母进行蛮力比较。
最佳答案
L - list of correct words of size n.
L'- list of incorrect words of size m.
H - hash table
R - result set
1. for each word w in L :
1.1 for each typo t of w : //there are l-1 typos
1.1.1 insert t into H
2. for each word w' in L' :
2.1 if w' in H insert w' in R
3. return R
时间复杂度:
O(n*l)+O(m) = O(max(n*l,m))
空间复杂度:
O(n*l)
关于java - 在单词列表中查找拼写错误，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12995038/