72. Edit Distance

Edit Distance

Problem Description

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

 

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

 

Constraints:

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

Approach) Dynamic Programming

1. Use the Levenshtein distance algorithm and dynamic programming implementation
2. Build a matrix from word1 and word2, each cell represents the minimum difference between the words up to the current character
3. Each cell is trying to become the local minimum difference, so we have 3 options, 1 + left cell, 1 + top cell, 1 + diagonal (two characters aren't the same), or 0 + diagonal (two characters are the same)
   
   

var minDistance = function(word1, word2) {
    let dp = Array(word1.length+1).fill(null).map(()=>(Array(word2.length+1).fill(0)));

    for (let i=0;i<dp.length;i++) {
        dp[i][0] = i
    }

    for (let i=0;i<dp[0].length;i++) {
        dp[0][i] = i
    }

    for (let i = 1;i<dp.length;i++) {
        for (let j=1;j<dp[0].length;j++) {
            dp[i][j] = Math.min(
                            dp[i-1][j]+1, // left
                            dp[i][j-1]+1, // right
                            dp[i-1][j-1] + (word1[i-1]!=word2[j-1]?1:0) // diagonal
                        );
        }
    }
    return dp[dp.length-1][dp[0].length-1];
};

Approach) Another way 

Minimum edit distance / Levenshtein Distance
What are the minimal # of edits (change, add, delete char) to convert 1 string to another
It's a DP problem, looking at one character at a time.

For each chacter, you either don't need to change it, you need to delete it, or you need to change it.
Keep doing that character after character for each possibility and since we are interested in the minimum number of changes, just keep track of the lowest #.

var minDistance = function(word1, word2) {
  let dp = Array(word1.length+1).fill().map(()=>Array(word2.length+1)); // Get our DP matrix setup, no need for default values since we'll be filling each each of them
  
  for (let r=0; r<=word1.length; r++) {
    for (let c=0; c<=word2.length; c++) {
      if (r==0) dp[0][c] = c; // here we setup the initial row
      else if (c==0) dp[r][0] = r; // here the initial column
      else if (word1[r-1] == word2[c-1]) //now, if the letter is the same, cost is the same as the upper left cost
        dp[r][c] = dp[r-1][c-1];
      else //letters are different, so we will either need to change or delete one of the letters so prev cost +1 operation
        dp[r][c] = Math.min(dp[r][c-1],dp[r-1][c-1], dp[r-1][c]) +1;
    }
  }
  return dp[word1.length][word2.length]; //return the cost at the end of the string
};

If this explanation helped, please upvote this post so others can notice it.

Conclusion

That’s all folks! In this post, we solved LeetCode problem 72. Edit Distance

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!