LeetCode: Edit Distance

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

---

We can use DP to solve this problem. Let dis[i][j] be the minimum distance from word1[0~i] to word2[0~j]. So if word1[i-1] is the same char as word2[j-1], dis[i][j] is equal to dis[i-1][j-1] since nothing is to be done with the last char. Otherwise we can reach dis[i][j] from dis[i-1][j], dis[i][j-1] and dis[i-1][j-1].

C++ Code:

/*
 * func: edit_distance
 * goal: find the minimum edit distance from word1 to word2
 * @param word1: word 1
 * @param word2: word 2
 * return: minimum distance
 */
/*
 * DP: dis[i][j] = min(dis[i][j-1], dis[i-1][j], dis[i-1][j-1]) + 1
 * complexity: time O(mn), space O(mn)
 */
int edit_distance(string word1, string word2){
    //dis[i][j] stands for the minimum step from word1[0-i] to word2[0-j]
    int dis[word1.length()+1][word2.length()+1];
    
    for(int i = 0; i <= word1.length(); i++){
        dis[i][0] = i;
    }
    for(int i = 0; i <= word2.length(); i++){
        dis[0][i] = i;
    }
    
    for(int i = 1; i <= word1.length(); i++){
        for(int j = 1; j <= word2.length(); j++){
            //If the current char is the same one, nothing to be edited again
            if(word1[i-1] ==  word2[j-1]){
                dis[i][j] = dis[i-1][j-1];
            }else{
                //we can reach [i][j] from [i-1][j] + 1 or [i][j-1] + 1 or [i-1][j-1] + 1
                dis[i][j] = std::min(dis[i-1][j-1], std::min(dis[i-1][j], dis[i][j-1])) + 1;
            }
        }
    }
    return dis[word1.length()][word2.length()];
}

Python Code:

# func: find the minimum steps need to transform word1 to word2
# @param word1: input word1
# @param word2: input word2
# @return: minimum distance
def edit_distance(word1, word2):
    if not word1:
        return len(word2)
    if not word2:
        return len(word1)

    dis = [[0] * (len(word1)+1) for _ in xrange(len(word2)+1)]

    for i in xrange(len(word1)+1):
        dis[i][0] = i
    for j in xrange(len(word2)+1):
        dis[0][j] = j

    for i in xrange(1, len(word1) + 1):
        for j in xrange(1, len(word2) + 1):
            if word1[i-1] ==  word2[j-1]:
                dis[i][j] = dis[i-1][j-1]
            else:
                dis[i][j] = min(dis[i-1][j], dis[i][j-1], dis[i-1][j-1]) + 1

    return dis[len(word1)][len(word2)]