Problem
You are given two stringsword1 and word2. Return the minimum number of operations required to convert word1 into word2.
The allowed operations are insert a character, delete a character, or replace a character.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
word1 = "horse"
word2 = "ros"Output
3Memoization Approach
We start at an index in both strings and determine the minimum operations needed to convert the remaining part ofword1 into the remaining part of word2.
If the current characters are equal, no operation is required, so we move to the next character in both strings.
If the characters are different, we have three choices: insert a character, delete the current character, or replace the current character.
For an insert, we move forward only in
word2. For a delete, we move forward only in word1. For a replace, we move forward in both strings.
We take the minimum of these three choices and add
1 for the current operation.
If one string is exhausted, the remaining characters in the other string must all be inserted or deleted.
The same pair of indices can be reached through different operations, so we store the result for each pair using memoization.
class Solution {
public int minDistance(String word1, String word2) {
int[][] memo = new int[word1.length()][word2.length()];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return editDistance(word1, word2, 0, 0, memo);
}
private int editDistance(String word1, String word2, int i, int j, int[][] memo) {
// Insert remaining characters.
if (i == word1.length()) {
return word2.length() - j;
}
// Delete remaining characters.
if (j == word2.length()) {
return word1.length() - i;
}
// Return the cached result.
if (memo[i][j] != -1) {
return memo[i][j];
}
// Characters already match.
if (word1.charAt(i) == word2.charAt(j)) {
return memo[i][j] = editDistance(word1, word2, i + 1, j + 1, memo);
}
// Insert, delete, or replace.
int insert = editDistance(word1, word2, i, j + 1, memo);
int delete = editDistance(word1, word2, i + 1, j, memo);
int replace = editDistance(word1, word2, i + 1, j + 1, memo);
return memo[i][j] = 1 + Math.min(insert, Math.min(delete, replace));
}
}
Complexity
There arem × n possible combinations of indices, and each combination is calculated only once, resulting in O(m × n) time complexity.
The memoization table requires
O(m × n) space, where m and n are the lengths of the two strings.
Tabulation Approach
We can also solve the problem using bottom-up Dynamic Programming.Let
dp[i][j] represent the minimum number of operations required to convert the first i characters of word1 into the first j characters of word2.
If
word1 is empty, we need j insertions. If word2 is empty, we need i deletions.
If the current characters are equal, no operation is required. Otherwise, we take the minimum of insert, delete, and replace.
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// Convert an empty word1 to word2.
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}
// Convert word1 to an empty word2.
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// Characters already match.
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
// Insert, delete, or replace.
dp[i][j] = 1 + Math.min(dp[i][j - 1],
Math.min(dp[i - 1][j], dp[i - 1][j - 1]));
}
}
}
return dp[m][n];
}
}
Complexity
The DP table containsm × n states, and each state is calculated once, resulting in O(m × n) time complexity. The DP table requires O(m × n) space.
Space Optimized Approach
In the tabulation approach, each value only depends on the previous row and the current row.Therefore, we can reduce the space complexity by using a single one-dimensional array. We keep the previous diagonal value separately because it represents
dp[i - 1][j - 1].
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[] dp = new int[n + 1];
// Convert an empty word1 to word2.
for (int j = 0; j <= n; j++) {
dp[j] = j;
}
for (int i = 1; i <= m; i++) {
int previous = dp[0];
// Convert word1 prefix to an empty word2.
dp[0] = i;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[j] = previous;
} else {
dp[j] = 1 + Math.min(dp[j - 1], Math.min(dp[j], previous));
}
previous = temp;
}
}
return dp[n];
}
}
Complexity
Each pair of characters is processed once, resulting inO(m × n) time complexity, while the one-dimensional DP array requires O(n) space.