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, Python, C++ and JavaScript, 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.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
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 code in Java, Python, C++ and JavaScript.
| 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)));
}
}class Solution:
def minDistance(self, a: str, b: str) -> int:
return self.f(a, b, len(a), len(b))
def f(self, a: str, b: str, i: int, j: int) -> int:
if i == 0:
return j
if j == 0:
return i
if a[i - 1] == b[j - 1]:
return self.f(a, b, i - 1, j - 1)
return 1 + min(self.f(a, b, i - 1, j - 1), min(self.f(a, b, i - 1, j), self.f(a, b, i, j - 1)))class Solution {
public:
int minDistance(string a, string b) {
return f(a, b, a.size(), b.size());
}
private:
int f(const string& a, const string& b, int i, int j) {
if (i == 0) return j;
if (j == 0) return i;
if (a[i - 1] == b[j - 1]) return f(a, b, i - 1, j - 1);
return 1 + min(f(a, b, i - 1, j - 1), min(f(a, b, i - 1, j), f(a, b, i, j - 1)));
}
};function minDistance(a, b) {
return f(a, b, a.length, b.length);
}
function f(a, b, i, j) {
if (i === 0) return j;
if (j === 0) return i;
if (a[i - 1] === b[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];
}
}class Solution:
def minDistance(self, a: str, b: str) -> int:
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = (dp[i - 1][j - 1] if a[i - 1] == b[j - 1]
else 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])))
return dp[m][n]class Solution {
public:
int minDistance(string a, string b) {
int m = a.size(), n = b.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
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[i - 1] == b[j - 1]
? dp[i - 1][j - 1]
: 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
return dp[m][n];
}
};function minDistance(a, b) {
const m = a.length, n = b.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) dp[i][0] = i;
for (let j = 0; j <= n; j++) dp[0][j] = j;
for (let i = 1; i <= m; i++)
for (let j = 1; j <= n; j++)
dp[i][j] = a[i - 1] === b[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];
}
}class Solution:
def minDistance(self, a: str, b: str) -> int:
m, n = len(a), len(b)
prev, cur = list(range(n + 1)), [0] * (n + 1)
for i in range(1, m + 1):
cur[0] = i
for j in range(1, n + 1):
cur[j] = (prev[j - 1] if a[i - 1] == b[j - 1]
else 1 + min(prev[j - 1], min(prev[j], cur[j - 1])))
prev, cur = cur, prev
return prev[n]class Solution {
public:
int minDistance(string a, string b) {
int m = a.size(), n = b.size();
vector<int> prev(n + 1), cur(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[i - 1] == b[j - 1]
? prev[j - 1]
: 1 + min(prev[j - 1], min(prev[j], cur[j - 1]));
swap(prev, cur);
}
return prev[n];
}
};function minDistance(a, b) {
const m = a.length, n = b.length;
let prev = new Array(n + 1).fill(0), cur = new Array(n + 1).fill(0);
for (let j = 0; j <= n; j++) prev[j] = j;
for (let i = 1; i <= m; i++) {
cur[0] = i;
for (let j = 1; j <= n; j++)
cur[j] = a[i - 1] === b[j - 1]
? prev[j - 1]
: 1 + Math.min(prev[j - 1], Math.min(prev[j], cur[j - 1]));
[prev, cur] = [cur, prev];
}
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).