Edit Distance

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