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
Examples:
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')Solution in Python:
To solve the Edit Distance problem, we need to determine the minimum number of operations required to convert one string (word1) into another string (word2). The operations allowed are insertion, deletion, and replacement of characters.
We will use dynamic programming to solve this problem. We will create a 2D table where dp[i][j] represents the minimum number of operations required to convert the first i characters of word1 into the first j characters of word2.
- Initialize the DP table: Create a table
dpwith dimensions(len(word1) + 1) x (len(word2) + 1).dp[i][j]will hold the edit distance between the firsticharacters ofword1and the firstjcharacters ofword2. - Base Cases:
- If
word1is empty, the only option is to insert all characters ofword2. So,dp[0][j] = j. - If
word2is empty, the only option is to delete all characters ofword1. So,dp[i][0] = i.
- If
- Fill the DP table:
- If the characters of
word1andword2match (word1[i-1] == word2[j-1]), then no new operation is needed, and we can take the value fromdp[i-1][j-1]. - If the characters do not match, we consider the minimum of three possible operations:
- Insert a character:
dp[i][j-1] + 1 - Delete a character:
dp[i-1][j] + 1 - Replace a character:
dp[i-1][j-1] + 1
- Insert a character:
- If the characters of
- Result: The value in
dp[len(word1)][len(word2)]will be our answer, i.e., the minimum number of operations required to convertword1toword2.
Python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
# Initialize the DP table with zeroes
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Fill the base cases
for i in range(1, m + 1):
dp[i][0] = i
for j in range(1, n + 1):
dp[0][j] = j
# Fill the rest of the DP table
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] + 1, # Delete
dp[i][j - 1] + 1, # Insert
dp[i - 1][j - 1] + 1) # Replace
# The answer is in the bottom-right corner of the DP table
return dp[m][n]Detailed Comments:
- Initialization:
dp = [[0] * (n + 1) for _ in range(m + 1)]initializes a 2D list with dimensions(m+1) x (n+1)filled with zeros. - Base Cases:
for i in range(1, m + 1): dp[i][0] = ifills the first column, representing the cost of deleting characters fromword1.for j in range(1, n + 1): dp[0][j] = jfills the first row, representing the cost of inserting characters fromword2.
- DP Table Filling:
- The nested loops iterate through each character of
word1andword2. if word1[i - 1] == word2[j - 1]: dp[i][j] = dp[i - 1][j - 1]checks if the characters are the same; if so, it takes the diagonal value.else: dp[i][j] = min(...)computes the minimum of insert, delete, and replace operations.
- The nested loops iterate through each character of
- Result:
return dp[m][n]gives the minimum edit distance.
This solution ensures that all possible operations are considered to find the minimum number of changes required.
Solution in Javascript:
JavaScript
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(word1, word2) {
let m = word1.length;
let n = word2.length;
// Initialize the DP table with dimensions (m+1) x (n+1)
let dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
// Fill the base cases
for (let i = 1; i <= m; i++) {
dp[i][0] = i; // Cost of deleting all characters from word1 to match an empty word2
}
for (let j = 1; j <= n; j++) {
dp[0][j] = j; // Cost of inserting all characters of word2 to match an empty word1
}
// Fill the DP table
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1.charAt(i - 1) === word2.charAt(j - 1)) {
// Characters match, no additional cost
dp[i][j] = dp[i - 1][j - 1];
} else {
// Calculate the minimum cost of insert, delete, or replace
dp[i][j] = Math.min(
dp[i - 1][j] + 1, // Delete
dp[i][j - 1] + 1, // Insert
dp[i - 1][j - 1] + 1 // Replace
);
}
}
}
// The answer is in the bottom-right corner of the DP table
return dp[m][n];
};Solution in Java:
Java
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// Initialize the DP table with dimensions (m+1) x (n+1)
int[][] dp = new int[m + 1][n + 1];
// Fill the base cases
for (int i = 1; i <= m; i++) {
dp[i][0] = i; // Cost of deleting all characters from word1 to match an empty word2
}
for (int j = 1; j <= n; j++) {
dp[0][j] = j; // Cost of inserting all characters of word2 to match an empty word1
}
// Fill the DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
// Characters match, no additional cost
dp[i][j] = dp[i - 1][j - 1];
} else {
// Calculate the minimum cost of insert, delete, or replace
dp[i][j] = Math.min(
dp[i - 1][j] + 1, // Delete
Math.min(
dp[i][j - 1] + 1, // Insert
dp[i - 1][j - 1] + 1 // Replace
)
);
}
}
}
// The answer is in the bottom-right corner of the DP table
return dp[m][n];
}
}Solution in C#:
C#
public class Solution {
public int MinDistance(string word1, string word2) {
int m = word1.Length;
int n = word2.Length;
// Initialize the DP table with dimensions (m+1) x (n+1)
int[,] dp = new int[m + 1, n + 1];
// Fill the base cases
for (int i = 1; i <= m; i++) {
dp[i, 0] = i; // Cost of deleting all characters from word1 to match an empty word2
}
for (int j = 1; j <= n; j++) {
dp[0, j] = j; // Cost of inserting all characters of word2 to match an empty word1
}
// Fill the DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1]) {
// Characters match, no additional cost
dp[i, j] = dp[i - 1, j - 1];
} else {
// Calculate the minimum cost of insert, delete, or replace
dp[i, j] = Math.Min(
dp[i - 1, j] + 1, // Delete
Math.Min(
dp[i, j - 1] + 1, // Insert
dp[i - 1, j - 1] + 1 // Replace
)
);
}
}
}
// The answer is in the bottom-right corner of the DP table
return dp[m, n];
}
}