我有一本包含“n”个单词的字典，并且有“m”个查询要响应。我想输出字典中编辑距离为 1 或 2 的单词数。鉴于 n 和 m 大约为 3000，我想优化结果集。
从下面的答案添加编辑：
我会尝试换一种说法。
最初有 'n' 个单词作为一组 Dictionary 单词给出。给出下一个“m”字，它们是查询词，对于每个查询词，我需要查找该词是否已存在于字典中（编辑距离“0”）或字典中位于编辑距离 1 或2 从字典单词。
我希望问题现在很清楚。
好吧，如果时间复杂度是 (m*n)n，它就会超时。DP 编辑距离算法的幼稚使用会超时。即使计算 2k+1 的对角元素也会超时，其中 k 是阈值，在上述情况下 k=3。
您想使用两个单词之间的Levenshtein 距离，但我假设您知道这一点，因为这就是问题标签所说的。
您必须遍历您的列表（假设）并将列表中的每个单词与您正在执行的当前查询进行比较。你可以建立一个BK-tree来限制你的搜索空间，但是如果你只有大约 3000 个单词，这听起来有点矫枉过正。
var upperLimit = 2;
var allWords = GetAllWords();
var matchingWords = allWords
.Where(word => Levenshtein(query, word) <= upperLimit)
.ToList();
在编辑原始问题后添加
如果您有不区分大小写的字典，则查找距离 = 0 的情况很容易包含查询。距离 <= 2 的情况需要对搜索空间进行完整扫描，每个查询词进行 3000 次比较。假设相同数量的查询词将导致 900 万次比较。
您提到它超时，所以我认为您配置了超时？您的速度可能是由于 Levenshtein 计算的实施不佳或缓慢吗？
（来源：itu.edu.tr）
上图是从CLiki 窃取的：bk-tree
正如所见，使用编辑距离 <= 2 的 bk-tree 只会访问大约 1% 的搜索空间，但这是假设您有非常大的输入数据，在他们的情况下多达 50 万个单词。在您的情况下，我会假设类似的数字，但是即使存储在列表/字典中，如此少量的输入也不会造成太大的麻烦。
我会尝试换一种说法。
最初有 'n' 个单词作为一组 Dictionary 单词给出。给出下一个“m”字，它们是查询词，对于每个查询词，我需要查找该词是否已存在于字典中（编辑距离“0”）或字典中位于编辑距离 1 或2 从字典单词。
我希望问题现在很清楚。
好吧，如果时间复杂度为 (m*n)*n，它就会超时。DP 编辑距离算法的天真使用会超时。即使计算 2*k+1 的对角线元素也会超时，其中 k 是上述情况下 k=3 的阈值。
PS：BK 树应该足以满足目的。关于 C++ 实现的任何链接。
public class Solution {
public int minDistance(String word1, String word2) {
int[][] table = new int[word1.length()+1][word2.length()+1];
for(int i = 0; i < table.length; ++i) {
for(int j = 0; j < table[i].length; ++j) {
if(i == 0)
table[i][j] = j;
else if(j == 0)
table[i][j] = i;
else {
if(word1.charAt(i-1) == word2.charAt(j-1))
table[i][j] = table[i-1][j-1];
else
table[i][j] = 1 + Math.min(Math.min(table[i-1][j-1],
table[i-1][j]), table[i][j-1]);
}
}
}
return table[word1.length()][word2.length()];
}
}