使用 O(n) space 问题编辑距离解决方案

Question

找到了几个不同的解决方案和调试，并且对下面的解决方案特别感兴趣，它只需要 O(n) space，而不是存储矩阵 (M*N)。但是对 cur[i] 的逻辑含义是什么感到困惑。如果有人有任何意见，我们将不胜感激。

我发布了解决方案和代码。

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

class Solution { 
public:
    int minDistance(string word1, string word2) {
        int m = word1.length(), n = word2.length();
        vector<int> cur(m + 1, 0);
        for (int i = 1; i <= m; i++)
            cur[i] = i;
        for (int j = 1; j <= n; j++) {
            int pre = cur[0];
            cur[0] = j;
            for (int i = 1; i <= m; i++) {
                int temp = cur[i];
                if (word1[i - 1] == word2[j - 1])
                    cur[i] = pre;
                else cur[i] = min(pre + 1, min(cur[i] + 1, cur[i - 1] + 1));
                pre = temp;
            }
        }
        return cur[m]; 
    }
};

Answer 1

您可以将 cur 视为编辑距离矩阵中上一行和当前行的混合。例如，想一想原始算法中的 3x3 矩阵。我将对每个位置进行编号，如下所示：

1 2 3
4 5 6
7 8 9

在循环中，如果计算位置 6，则只需要 2、3 和 5 的值。在这种情况下，cur 将恰好是以下值：

4 5 3

最后看到3了吗？那是因为我们还没有更新它，所以它仍然有第一行的值。从上一次迭代中，我们有 pre = 2，因为它是在我们计算 5 处的值之前保存的。

那么，最后一个单元格的新值是 pre = 2、cur[i-1] = 5 和 cur[i] = 3 中的最小值，正好是前面提到的值。

编辑：完成类比，如果在 O(n^2) 版本中你计算 min(M[i-1][j-1], M[i][j-1], M[i-1][j])，在这个 O(n) 版本中你将分别计算 min(pre, cur[i-1], cur[i])。

使用 O(n) space 问题编辑距离解决方案

edit distance solution with O(n) space issue

c++

algorithm

edit-distance