#72
Edit Distance
Medium 2D DP on two strings
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the minimum number of single-character inserts, deletes and replacements needed to turn word1 into word2.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: fewest inserts, deletes and replaces to turn one word into another.
Why this works: dp[i][j] for prefixes: same letter → no cost; otherwise 1 + the best of replace, delete or insert.
Example: "horse" → "ros"
horse → rorse (replace h) → rose (delete r) → ros (delete e) → 3✦Hints open one at a time
dp[i][j] = edits to turn the first i chars of word1 into the first j chars of word2.
Equal last chars: dp[i−1][j−1]. Otherwise 1 + min(replace dp[i−1][j−1], delete dp[i−1][j], insert dp[i][j−1]).
Base cases: dp[i][0] = i, dp[0][j] = j.
↗Approach
Fill the table row by row with the transition above.
</>Solution (Java)
class Solution {
public int minDistance(String a, String b) {
int n = a.length(), m = b.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) dp[i][0] = i; // delete everything
for (int j = 0; j <= m; j++) dp[0][j] = j; // insert everything
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.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[n][m];
}
}!Common mistake
Forgetting the base row/column, so converting to or from an empty string costs 0.
Complexity
- Time: O(n·m).
- Space: O(n·m).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon