Solution For Edit Distance
The Edit Distance problem on LeetCode is also known as the minimum edit distance problem or the Levenshtein distance problem. It is a classic problem in computer science that deals with finding the minimum number of operations required to convert one string into another. These operations include insertion, deletion, and substitution of characters.
The problem statement on LeetCode is as follows:
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
Let’s take an example to understand the problem better.
Example 1:
Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
– Replace ‘h’ with ‘r’
– Delete ‘o’
– Delete ‘e’
One approach to solving this problem is to use dynamic programming. We can create a 2-D array dp where dp[i][j] represents the minimum number of operations required to convert the substring word1[0…i-1] to the substring word2[0…j-1].
We can fill up the table in a bottom-up manner. Here’s how the dp array would be filled:
- Initialization: dp[0][0] = 0, dp[i][0] = i (0<=i<=len(word1)), dp[0][j] = j (0<=j<=len(word2))
- If the characters at word1[i-1] and word2[j-1] are equal, then dp[i][j] = dp[i-1][j-1]
- If the characters at word1[i-1] and word2[j-1] are not equal, then dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
- dp[i-1][j] represents the cost of deleting the character from word1.
- dp[i][j-1] represents the cost of inserting the character into word1.
- dp[i-1][j-1] represents the cost of replacing the character in word1 with the character in word2.
The final answer will be stored in dp[len(word1)][len(word2)].
Here’s the Python code for the Edit Distance problem:
“`
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
# initialization
for i in range(m+1):
dp[i][0] = i
for j in range(n+1):
dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
return dp[m][n]
“`
The time complexity of the above algorithm is O(mn) where m and n are the lengths of word1 and word2 respectively. The space complexity is also O(mn) since we are using a 2-D array to store the intermediate results.
Step by Step Implementation For Edit Distance
class Solution {
public int minDistance(String word1, String word2) {
// if one of the strings is empty
if (word1.length() == 0 || word2.length() == 0) {
// return the length of the other string
return word1.length() == 0 ? word2.length() : word1.length();
}
// create a 2D array to store the edit distances
// for all substrings of word1 and word2
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
// initialize the 2D array
// the edit distance between an empty string and
// a non-empty string is the length of the non-empty string
for (int i = 0; i <= word1.length(); i++) {
dp[i][0] = i;
}
for (int j = 0; j <= word2.length(); j++) {
dp[0][j] = j;
}
// fill in the 2D array
// i and j represent the lengths of the substrings
// of word1 and word2 respectively
for (int i = 1; i <= word1.length(); i++) {
for (int j = 1; j <= word2.length(); j++) {
// if the ith character of word1 equals the
// jth character of word2
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
// then the edit distance between the
// ith and jth substrings of word1 and word2
// is the same as the edit distance between
// the (i - 1)th and (j - 1)th substrings
dp[i][j] = dp[i - 1][j - 1];
} else {
// otherwise, the edit distance is the minimum
// of the edit distances between the (i - 1)th
// and jth substrings, the ith and (j - 1)th
// substrings, and the (i - 1)th and (j - 1)th
// substrings, plus 1
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
}
}
// return the edit distance between word1 and word2
return dp[word1.length()][word2.length()];
}
}def minDistance(word1, word2):
# Create a table to store results of subproblems
dp = [[0 for x in range(len(word2)+1)] for x in range(len(word1)+1)]
# Fill d[][] in bottom up manner
for i in range(len(word1)+1):
for j in range(len(word2)+1):
# If first string is empty, only option is to
# insert all characters of second string
if i == 0:
dp[i][j] = j # Min. operations = j
# If second string is empty, only option is to
# remove all characters of second string
elif j == 0:
dp[i][j] = i # Min. operations = i
# If last characters are same, ignore last char
# and recur for remaining string
elif word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
# If the last character is different, consider all
# possibilities and find the minimum
else:
dp[i][j] = 1 + min(dp[i][j-1], # Insert
dp[i-1][j], # Remove
dp[i-1][j-1]) # Replace
return dp[len(word1)][len(word2)]var minDistance = function(word1, word2) {
// create a matrix to store the results of each subproblem
// (i.e. the edit distance between each prefix of word1 and
// each prefix of word2)
let matrix = [];
// fill in the first row and column of the matrix
for (let i = 0; i <= word1.length; i++) {
matrix.push([]);
matrix[i][0] = i;
}
for (let j = 0; j <= word2.length; j++) {
matrix[0][j] = j;
}
// fill in the rest of the matrix
for (let i = 1; i <= word1.length; i++) {
for (let j = 1; j <= word2.length; j++) {
// if the ith character of word1 equals the jth character of word2
// then the edit distance between the prefixes word1[0..i] and word2[0..j]
// is the same as the edit distance between the prefixes word1[0..i-1] and word2[0..j-1]
if (word1[i-1] === word2[j-1]) {
matrix[i][j] = matrix[i-1][j-1];
}
// otherwise, the edit distance is one more than the minimum of
// the edit distances between the prefixes word1[0..i-1] and word2[0..j],
// between the prefixes word1[0..i] and word2[0..j-1], and
// between the prefixes word1[0..i-1] and word2[0..j-1]
else {
matrix[i][j] = Math.min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1]) + 1;
}
}
}
// return the edit distance between the full strings word1 and word2
return matrix[word1.length][word2.length];
};int minDistance(string word1, string word2)
{
int len1 = word1.size();
int len2 = word2.size();
// len1+1, len2+1, because finally return dp[len1][len2]
int dp[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= len2; j++) {
dp[0][j] = j;
}
//iterate though, and check last char
for (int i = 0; i < len1; i++) {
char c1 = word1[i];
for (int j = 0; j < len2; j++) {
char c2 = word2[j];
//if last two chars equal
if (c1 == c2) {
//update dp value for +1 length
dp[i + 1][j + 1] = dp[i][j];
} else {
int replace = dp[i][j] + 1;
int insert = dp[i][j + 1] + 1;
int delete = dp[i + 1][j] + 1;
int min = replace > insert ? insert : replace;
min = delete > min ? min : delete;
dp[i + 1][j + 1] = min;
}
}
}
return dp[len1][len2];
}public class Solution {
public int MinDistance(string word1, string word2) {
int n = word1.Length;
int m = word2.Length;
// Create a table to store results of subproblems
int[,] dp = new int[n + 1, m + 1];
// Fill d[][] in bottom up manner
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
// If first string is empty, only option is to
// insert all characters of second string
if (i == 0)
dp[i, j] = j; // Min. operations = j
// If second string is empty, only option is to
// remove all characters of second string
else if (j == 0)
dp[i, j] = i; // Min. operations = i
// If last characters are same, ignore last char
// and recur for remaining string
else if (word1[i - 1] == word2[j - 1])
dp[i, j] = dp[i - 1, j - 1];
// If the last character is different, consider all
// possibilities and find the minimum
else
dp[i, j] = 1 + Math.Min(dp[i, j - 1], // Insert
Math.Min(dp[i - 1, j], // Remove
dp[i - 1, j - 1])); // Replace
}
}
return dp[n, m];
}
}