Edit Distance [Leetcode]

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

Solution: this is a famous DP problem which is well-explained in MIT Open Course. One thing which should be noted is that we can use linear space to solve the problem instead of two-dimensional cache like previous question.

class Solution {
public:
    int minDistance(string word1, string word2) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> cache(m+1, vector<int>(n+1,0));
        for(int i=0; i<=m; ++i){
            for(int j=0; j<=n; ++j){
                if(i==0 && j!=0)
                    cache[i][j]=j;
                if(i!=0 && j==0)
                    cache[i][j]=i;
                if(i!=0 && j!=0){
                    if(word1[i-1]==word2[j-1])
                        cache[i][j] = cache[i-1][j-1];
                    else
                        cache[i][j] = min(cache[i-1][j-1], min(cache[i-1][j], cache[i][j-1]))+1;
                }
            }
        }
        return cache[m][n];
    }
};