Last updated on October 9th, 2024 at 10:46 pm

Here, We see Edit Distance LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Edit Distance LeetCode Solution

Problem Statement

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')

1. Edit Distance Leetcode Solution C++

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

2. Edit Distance Leetcode Solution Java

class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            throw new IllegalArgumentException("Input strings are null");
        }
        int insertCost = 1;
        int deleteCost = 1;
        int replaceCost = 1;
        int l1 = word1.length();
        int l2 = word2.length();
        if (l1 == 0) {
            return l2 * insertCost;
        }
        if (l2 == 0) {
            return l1 * deleteCost;
        }
        if (l1 > l2) {
            return minDistance(word2, word1);
        }
        int[] dp = new int[l1 + 1];
        for (int i = 1; i <= l1; i++) {
            dp[i] = dp[i - 1] + deleteCost;
        }
        for (int j = 1; j <= l2; j++) {
            int prev = dp[0];
            dp[0] += insertCost; // l1 is blank, Inserting l2 chars in l1.
            char c2 = word2.charAt(j - 1);
            for (int i = 1; i <= l1; i++) {
                char c1 = word1.charAt(i - 1);
                int temp = dp[i];
                if (c1 == c2) {
                    dp[i] = prev;
                } else {
                    dp[i] = Math.min(prev + replaceCost, Math.min(dp[i - 1] + deleteCost, dp[i] + insertCost));
                }
                prev = temp;
            }
        }

        return dp[l1];        
    }
}

3. Edit Distance Leetcode Solution JavaScript

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];    
};

4. Edit Distance Leetcode Solution Python

class Solution(object):
    def minDistance(self, word1, word2):
        h, w = len(word1)+1, len(word2)+1
        pre = [i for i in range(w)]
        for i in range(1, h):
            cur = [i for _ in range(w)]
            for j in range(1, w):
                cur[j] = min(pre[j-1]+(word1[i-1] != word2[j-1]), pre[j]+1, cur[j-1]+1)
            pre = cur
        return pre[-1]
    
    # O(m*n) space
    def minDistance1(self, word1, word2):
        h, w = len(word1)+1, len(word2)+1
        dp = [[0 for _ in range(w)] for _ in range(h)]
        for i in range(h):
            dp[i][0] = i
        for j in range(w):
            dp[0][j] = j
        for i in range(1, h):
            for j in range(1, w):
                dp[i][j] = min(dp[i-1][j-1]+(word1[i-1]!=word2[j-1]), dp[i-1][j]+1, dp[i][j-1]+1)
        return dp[-1][-1]