Edit Distance
The Edit Distance (Levenshtein Distance) problem finds the minimum number of operations (insert, delete, replace) to convert one string into another. It's a classic DP problem with O(m*n) time.
Recurrence: dp[i][j] =
if s1[i-1] == s2[j-1]: dp[i-1][j-1]
else: 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
Java implementation:
public static int editDistance(String s1, String s2) {
int m = s1.length(), n = s2.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 (s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = 1 + Math.min(dp[i-1][j], // delete
Math.min(dp[i][j-1], // insert
dp[i-1][j-1])); // replace
}
}
}
return dp[m][n];
}
Two Minute Drill
- Edit distance = minimum operations to transform one string to another.
- Operations: insert, delete, replace.
- Time O(mn), space O(mn) (can be optimized to O(min(m,n))).
- Used in spell checkers, DNA sequence alignment.
Need more clarification?
Drop us an email at career@quipoinfotech.com