带O（n）空间问题的编辑距离问题

找到了几个不同的解决方案和调试方法，尤其对下面只需要O（n）空间的解决方案感兴趣，而不是存储矩阵（M * N）。但是对cur [i]的逻辑意义感到困惑。如果有人有任何意见，将不胜感激。带O（n）空间问题的编辑距离问题

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

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]; 
    } 
};

来源

2015-10-19 Lin Ma

您可以将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])。

来源

2015-10-19 01:06:43

谢谢胡安，真棒回复。我能否以这种方式理解pre，前一个任务中的pre手段（从word [0：i-1]转换为word [0：j-1]），最小操作是什么？假设当前任务是将字[0：i]转换为[0：j]？ –

嗨胡安，如果你可以评论我的上述问题，它会很好。 :) –

@ LinMa我做了一个编辑。 'pre'的意思就是在原始算法中：'M [i-1] [j-1]'。也就是说，在最小编辑距离计算的情况下，'pre + 1'是最后一个字符（字[0：1]）到字[0：j-1]我]改为[j]）“。 –

带O（n）空间问题的编辑距离问题

回答

相关问题