Edit Distance
Edit Distance is a medium dynamic programming problem solved with the strings pattern.
The best approach, optimal (two rows), runs in O(m · n) time and O(n) space.
Below are 3 approaches in Java, from recursion up.
Problem
Return the minimum number of operations (insert a character, delete a character, or replace a character) needed to turn word1 into word2.
Examples
Example 1
- Input
word1 = "horse", word2 = "ros"- Output
3- Why
- horse → rorse (replace) → rose (delete) → ros (delete).
Example 2
- Input
word1 = "", word2 = "abc"- Output
3
Constraints
0 <= length <= 500; lowercase letters.- Operations: insert, delete or replace one character.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Recursion | O(3^(m + n)) | O(m + n) |
| Tabulation (2D) | O(m · n) | O(m · n) |
| Optimal (two rows) | O(m · n) | O(n) |
1Recursion
O(3^(m + n))O(m + n)Compare the last characters. Equal: move both. Different: try insert (i, j - 1), delete (i - 1, j) and replace (i - 1, j - 1), each costing 1.
- f(0, j) = j; f(i, 0) = i.
class Solution {
public int minDistance(String a, String b) {
return f(a, b, a.length(), b.length());
}
private int f(String a, String b, int i, int j) {
if (i == 0) return j;
if (j == 0) return i;
if (a.charAt(i - 1) == b.charAt(j - 1)) return f(a, b, i - 1, j - 1);
return 1 + Math.min(f(a, b, i - 1, j - 1), Math.min(f(a, b, i - 1, j), f(a, b, i, j - 1)));
}
}2Tabulation (2D)
O(m · n)O(m · n)Fill the (m + 1) × (n + 1) table. Row 0 and column 0 are the costs of building from or deleting down to an empty string.
- dp[i][0] = i; dp[0][j] = j.
- Match: dp[i - 1][j - 1]. Else 1 + min of the three neighbours.
class Solution {
public int minDistance(String a, String b) {
int m = a.length(), n = b.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++)
dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
? dp[i - 1][j - 1]
: 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
return dp[m][n];
}
}3Optimal (two rows)
O(m · n)O(n)Each row depends only on the row above, so keep two rows and swap them.
- prev = row i - 1, cur = row i; cur[0] = i.
class Solution {
public int minDistance(String a, String b) {
int m = a.length(), n = b.length();
int[] prev = new int[n + 1], cur = new int[n + 1];
for (int j = 0; j <= n; j++) prev[j] = j;
for (int i = 1; i <= m; i++) {
cur[0] = i;
for (int j = 1; j <= n; j++)
cur[j] = a.charAt(i - 1) == b.charAt(j - 1)
? prev[j - 1]
: 1 + Math.min(prev[j - 1], Math.min(prev[j], cur[j - 1]));
int[] t = prev; prev = cur; cur = t;
}
return prev[n];
}
}Edge cases to test
- One string empty
- Identical strings (0)
Hints
Hint 1
dp[i][j] = edits to turn the first i chars of word1 into the first j chars of word2. If the last characters match, it is dp[i - 1][j - 1]; otherwise 1 + min(insert, delete, replace).
FAQ
What is the best time complexity for Edit Distance?
Optimal (two rows) runs in O(m · n) time and O(n) extra space.
Which pattern does Edit Distance use?
It is a dynamic programming problem that uses the strings pattern. Other problems with the same pattern: Longest Common Subsequence, Longest Palindromic Subsequence, Minimum Insertion Steps to Make a String Palindrome.
Is there a brute force solution for Edit Distance?
Yes. Recursion takes O(3^(m + n)) time and O(m + n) space. Compare the last characters.
Which edge cases should I test for Edit Distance?
One string empty; Identical strings (0).