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, or replace a character.
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: horse → rorse (replace 'h' with 'r') → rose (delete 'r') → ros (delete 'e').
Input: word1 = "intention", word2 = "execution"
Output: 5
We build a 2D DP table where dp[i][j] represents the minimum edit distance to convert the first i
characters of word1 to the first j characters of word2.
- Base cases: dp[i][0] = i (delete all characters) and dp[0][j] = j (insert all characters).
- If characters match: dp[i][j] = dp[i-1][j-1].
- If characters differ: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) representing delete, insert, and replace respectively.
- The answer is dp[m][n] where m and n are the lengths of the two words.
public class EditDistance {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
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.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
Math.min(dp[i - 1][j], dp[i][j - 1]));
}
}
}
return dp[m][n];
}
}
Complexity Analysis:
Time complexity: O(m * n) where m and n are the lengths of the two words.
Space complexity: O(m * n) for the 2D DP table; can be optimized to O(min(m,n)) using two rows.