Edit Distance
Given two words word1 and word2, find the minimum number of operations (insertions, deletions and substitutions) required to change word1 into word2.
Constraints:
- 0 <= word1.length, word2.length <= 500
- word1 and word2 consist of lowercase English letters
Examples:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: intention -> inention (remove 't') -> enention (remove 'i') -> exention (replace 'n' with 'x') -> exection (replace 'n' with 'x') -> execution (insert 'c')
Solutions
Dynamic Programming
The dynamic programming approach involves creating a 2D array dp where dp[i][j] represents the minimum number of operations required to change the first i characters of word1 into the first j characters of word2. The base cases are when one of the words is empty, in which case the minimum number of operations is the length of the non-empty word. For the recursive case, if the current characters in word1 and word2 are the same, then the minimum number of operations is the same as the minimum number of operations for the substrings without the current characters. If the current characters are different, then the minimum number of operations is 1 plus the minimum of the minimum number of operations for the substrings without the current character in word1, without the current character in word2, and without the current characters in both word1 and word2.
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 0;
i <= m;
i++) {
dp[i][0] = i;
}
for (int j = 0;
j <= n;
j++) {
dp[0][j] = j;
}
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 - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
}
}
}
return dp[m][n];
}Follow-up:
What if the operations are not limited to insertions, deletions, and substitutions, but also include transpositions (swapping two adjacent characters)?
