LeetCode 72. Edit Distance [Analysis]

The problem that I’ll discuss in this post is the Edit Distance . Again this problem is categorized as Hard, but it is in fact a very well known standard dynamic programming problem.

The edit distance algorithm is actually widely used in many areas of computer science, such as natural language processing, information theory and bioinformatics. Edit Distance is often called the Levenshtein Distance (especially when you are studying nlp) and there are variations to the Levenshtein Distance where one operation could be more costly than the other (but we don’t have to worry about this for this problem haha).

The basic idea for solving this problem is to construct a recursive relationship then apply dynamic programming to reduce overlapping subproblems. Suppose solve(i,j) represents the minimum edit distance for the substrings s[0…i-1] and t[0…j-1]. Then it is easy to see that:

If s[i] == t[j]:
solve(i,j) = solve(i-1,j-1)
Else if s[i] != t[j]:
solve(i,j) = min(solve(i-1,j)+1,solve(i,j-1)+1,solve(i-1,j-1)+1)

Note that solve(i-1,j) represents the deletion operation (we are geeting rid of the ith character of s), solve(i,j-1) represents the insertion operation (we are adding t[j] to s) and solve(i-1,j-1) is the substitution/replacement operation. Using this recursive relationship we program a bottom-up dp solution as below.

The Time complexity of the code is O(nm). Where |s| = n, |t| = m.

C++ Code:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size(); 
        int dp[n+1][m+1];  
        for (int i = 0; i <= n; i++){
            for (int j = 0; j <= m; j++){
                if (i == 0) dp[i][j] = j; 
                else if (j == 0) dp[i][j] = i; 
                else if (word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1]; 
                }else{
                    dp[i][j] = 1+min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]));  
                }
            }
        }
        return dp[n][m];  
    }
};