给定长度为l的正确单词列表和长度为l的错误单词列表,通过交换两个连续字母,找到不同于错误单词列表的单词与纠正单词列表不同.这些话被认为是拼写错误.例如,hte被认为是一个错字,而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 * 1)
