edit distance solution with O(n) space issue

Question

Found a few different solutions and debugging, and especially interested in below solution which requires only O(n) space, other than store a matrix (M*N). But confused about what is the logical meaning of cur[i]. If anyone have any comments, it will be highly appreciated.

I posted solution and code.

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

You can think of cur as being as a mix of the previous line and the current line in the edit distance matrix. For example, think of a 3x3 matrix in the original algorithm. I'll number each position like below:

1 2 3
4 5 6
7 8 9

In the loop, if you are computing the position 6, you only need the values from 2, 3 and 5. In that case, cur will be exactly the values from:

4 5 3

See the 3 in the end? That's because we didn't updated it yet, so it still has a value from the first line. From the previous iteration, we have pre = 2, because it was saved before we computed the value at 5.

Then, the new value for the last cell is the minimum of pre = 2, cur[i-1] = 5 and cur[i] = 3, exactly the values mentioned before.

EDIT: completing the analogy, if in the O(n^2) version you compute min(M[i-1][j-1], M[i][j-1], M[i-1][j]), in this O(n) version you'll compute min(pre, cur[i-1], cur[i]), respectively.