Edit Distance

Q:
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
T:
Suppose word1[i] == word2[j], then the distance equals the distance of word1.substr(0, i) and word2.substr(0, j). Otherwise, the distance is one plus the distance of three combinations: word1.substr(0, i) and word2.substr(0, j) by replacing word1[i] with word2[j], word1.substr(0, i+1) and word2.substr(0, j) by adding word2[j] at the end, word1.substr(0, i) and word2.substr(0, j+1) by deleting word1[i] at the end. Let c[i][j] notes the distance between word1.substr(0, i) and word2.substr(0, j), it is:
c[0][j] = j;
c[i][0] = i;
c[i][j] = c[i-1][j-1], if word1[i-1] == word2[j-1]
             1 + min(c[i-1][j-1], c[i-1][j], c[i][j-1]), else

A:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int * cur = new int[word2.size()+1];
        for(int i=0; i<=word2.size(); i++) {
            cur[i] = i;
        }
        for(int i=1; i<=word1.size(); i++) {
            int tmp = i-1;
            cur[0] = i;
            for(int j=1; j<=word2.size(); j++) {
                int tmp2 = cur[j];
                if(word1[i-1] == word2[j-1]) {
                    cur[j] = tmp;
                    tmp = tmp2;
                } else {
                    cur[j] = min(min(cur[j], cur[j-1]), tmp) + 1;
                    tmp = tmp2;
                }
            }
        }
        int ret = cur[word2.size()];
        delete[] cur;
        return ret;
    }
};