在单词列表中查找拼写错误

Question

给定所有长度l的正确单词列表和长度l不正确的单词列表,通过交换两个连续字母,找到不正确单词列表中的单词与纠正单词列表不同.这些话被认为是拼写错误.例如,hte被认为是错字,the而不het被视为错别字.

什么是最佳时间效率算法,允许我们通过这个定义找到被认为是拼写错误的单词列表？

我被告知列表可以在线性时间内计算,但我没有找到线性时间的解决方案.我能想到的唯一方法是比较来自一个列表的所有字母与另一个列表的强力.

Answer 1

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)