edit distance solution with O (n) space issue

Question

Нашли несколько различных решений и отладки, и особенно заинтересованы в нижеприведенном решении, которое требует только O (n) пространства, кроме хранения матрицы (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, точно значение упоминалось ранее.

EDIT: завершение аналогий, если в версии 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]), соответственно.