c# - 这个 Levenshtein 距离算法是否正确？

Question

我已经编写了下面的算法来计算 Levenshtein 距离，根据我的测试，它似乎返回了正确的结果。时间复杂度为O(n+m)，空间为O(1)。

我所见过的所有现有算法的空间复杂度都是 O(n*m)，因为它们创建了一个矩阵。我的算法有问题吗？

public static int ComputeLevenshteinDistance(string word1, string word2)
{
    var index1 = 0;
    var index2 = 0;
    var numDeletions = 0;
    var numInsertions = 0;
    var numSubs = 0;
    while (index1 < word1.Length || index2 < word2.Length)
    {
        if (index1 == word1.Length)
        {
            // Insert word2[index2]
            numInsertions++;
            index2++;
        }
        else if (index2 == word2.Length)
        {
            // Delete word1[index1]
            numDeletions++;
            index1++;
        }
        else if (word1[index1] == word2[index2])
        {
            // No change as word1[index1] == word2[index2]
            index1++;
            index2++;
        }
        else if (index1 < word1.Length - 1 && word1[index1 + 1] == word2[index2])
        {
            // Delete word1[index1]
            numDeletions++;
            index1++;
        }
        else if (index2 < word2.Length - 1 && word1[index1] == word2[index2 + 1])
        {
            // Insert word2[index2]
            numInsertions++;
            index2++;
        }
        else
        {
            // Substitute word1[index1] for word2[index2]
            numSubs++;
            index1++;
            index2++;
        }
    }

    return numDeletions + numInsertions + numSubs;
}

Answer 1

是评论，但我觉得它可能适合作为答案:

如果您想要任何给定输入的真正最短距离，简短的回答是“否”。

您的代码看起来更高效的原因(以及其他实现创建矩阵而不是执行您正在做的事情的原因)是您的逐步实现忽略了很多潜在的解决方案。

@BenVoigt 给出的示例说明了这一点，另一个可能更清楚的说明是 ("aaaardvark", "aardvark") 返回 8，应该是 2:它被绊倒了，因为它匹配第一个 a 并认为它可以继续前进，而实际上更优化的解决方案是考虑前两个字符插入。