72. Edit Distance
Last updated
Last updated
/**
* Time complexity : O(mn) as it follows quite straightforward for the inserted loops.
* Space complexity : O(mn) since at each step we keep the results of all
* previous computations.
*/
class Solution {
public int minDistance(String word1, String word2) {
int w1Len = word1.length();
int w2Len = word2.length();
// if one of the strings is empty
if(w1Len * w2Len == 0) return w1Len + w2Len;
int[][] dp = new int[w2Len+1][w1Len+1];
// init boundaries
for(int i = 0; i <= w1Len; i++) {
dp[0][i] = i;
}
for(int i = 0; i <= w2Len; i++) {
dp[i][0] = i;
}
// DP compute
for(int i = 1; i <= w2Len; i++) {
for(int j = 1; j <= w1Len; j++) {
if(word2.charAt(i-1) == word1.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = Math.min(dp[i-1][j-1],
Math.min(dp[i-1][j], dp[i][j-1])) + 1;
}
}
}
return dp[w2Len][w1Len];
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
int[][] dp;
public int minDistance(String a, String b) {
int n = a.length(), m = b.length();
dp = new int[a.length()][b.length()];
return f(n-1, m-1, a, b);
}
public int f(int i, int j, String a, String b) {
if (i < 0) return j+1;
if (j < 0) return i+1;
if (dp[i][j] != 0) return dp[i][j];
if (a.charAt(i) == b.charAt(j)) {
dp[i][j] = f(i-1, j-1, a, b);
} else {
dp[i][j] = 1 + Math.min(f(i-1, j-1, a, b) ,
Math.min(f(i-1, j, a, b), f(i, j-1, a, b)));
}
return dp[i][j];
}
}