Last updated on January 19th, 2025 at 02:46 am
Here, we see an Edit Distance LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Dynamic Programming, String
Level of Question
Medium
Edit Distance LeetCode Solution
Table of Contents
1. 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')
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Dynamic Programming. Specifically, this problem is a variation of the Longest Common Subsequence (LCS) problem, which is solved using a 2D DP table or 1D DP array to compute the minimum edit distance between two strings. The problem involves breaking it into subproblems and solving them iteratively or recursively while storing intermediate results to avoid redundant computations.
3. Code Implementation in Different Languages
3.1 Edit Distance 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];
}
};
3.2 Edit Distance 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.3 Edit Distance 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];
};
3.4 Edit Distance 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]
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(m * n) | O(m * n) |
| Java | O(m * n) | O(min(m, n)) |
| JavaScript | O(m * n) | O(m * n) |
| Python | O(m * n) | O(m * n) |
- The time complexity is O(m * n) for all implementations because:
- The outer loop iterates over the length of
word1(m). - The inner loop iterates over the length of
word2(n). - For each pair of characters, a constant amount of work is done (comparison and minimum calculation).
- The outer loop iterates over the length of
- C++ and JavaScript: Use a 2D DP table of size
(m+1) x (n+1), resulting in O(m * n) space. - Java: Uses a 1D DP array of size
min(m, n)for space optimization, resulting in O(min(m, n)) space. - Python: Two implementations:
- The first uses a 1D DP array of size
n, resulting in O(n) space. - The second uses a 2D DP table of size
(m+1) x (n+1), resulting in O(m * n) space.
- The first uses a 1D DP array of size