Edit distance between two strings
Given two strings a and b, return the smallest number of
single-character operations that turn a into b. The allowed operations are
inserting a character, deleting a character and replacing one character with another.
Examples
| Input | Output | Why |
|---|---|---|
a = "horse", b = "ros" | 3 | horse → rorse (replace h) → rose (delete r) → ros (delete e). |
a = "kitten", b = "sitting" | 3 | Two replacements and one insertion. |
a = "abc", b = "" | 3 | Delete everything. |
Constraints
- 0 ≤ |a|, |b| ≤ 500
- Lowercase letters
Hints
Hint 1
Look at the last characters. If they are equal, they can be left alone, and the problem shrinks to the two shorter prefixes.
Hint 2
If they differ, the last operation is one of three: replace a's last character with b's, delete a's last character, or insert b's last character. Each leaves a smaller problem on prefixes.
Hint 3
Let d[i][j] be the distance between the first i characters of a and the first j of b. Fill the table from d[0][j] = j and d[i][0] = i; only the previous row is needed at any time.
Where people lose marks
- Treating a match as free but still adding 1 for it. When the last characters are equal, the cell copies its diagonal neighbour with no cost.
- Overwriting the diagonal value too early when compressing to one row: save d[i−1][j−1] before writing d[i][j−1].
- Forgetting the edges. d[i][0] = i is not zero; turning "abc" into "" costs 3.
- Indexing the strings with the table's indices: d[i][j] looks at a[i−1] and b[j−1], because row and column 0 stand for the empty prefix.
Dry run on "horse","ros"
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 6"" → prefixes of "ros"00112233
Row 0: turning the empty prefix of "horse" into the first j characters of "ros" takes j insertions.
-
Step 2 / 6row 000112233row 1 ("h")10112233distance so far3
Row 1: the prefix "h". Each cell takes the diagonal value when the last letters match, and otherwise 1 plus the smallest of diagonal, above and left.
-
Step 3 / 6row 110112233row 2 ("ho")20211223distance so far2
Row 2: the prefix "ho". Each cell takes the diagonal value when the last letters match, and otherwise 1 plus the smallest of diagonal, above and left.
-
Step 4 / 6row 220211223row 3 ("hor")30212223distance so far2
Row 3: the prefix "hor". Each cell takes the diagonal value when the last letters match, and otherwise 1 plus the smallest of diagonal, above and left.
-
Step 5 / 6row 330212223row 4 ("hors")40313223distance so far2
Row 4: the prefix "hors". Each cell takes the diagonal value when the last letters match, and otherwise 1 plus the smallest of diagonal, above and left.
-
Step 6 / 6row 440313223row 5 ("horse")50414233distance so far3
Row 5: the prefix "horse". Each cell takes the diagonal value when the last letters match, and otherwise 1 plus the smallest of diagonal, above and left. The bottom-right cell is the answer: 3.
How to think about it
Define d[i][j] as the edit distance between a[:i] and
b[:j]. Consider the last characters of the two prefixes.
- If
a[i−1] = b[j−1], an optimal edit leaves them alone:d[i][j] = d[i−1][j−1]. - Otherwise one operation deals with them, and the rest is a smaller problem:
d[i][j] = 1 + min(d[i−1][j−1], d[i−1][j], d[i][j−1]), for a replacement, a deletion fromaand an insertion ofb[j−1].
The edges are fixed: turning a prefix into the empty string takes as many deletions as it has
characters, so d[i][0] = i and d[0][j] = j. Each cell depends only on the
cell above, the cell to the left and the cell diagonally above-left, so filling the table row by row
needs two rows of memory, O(|b|).
Most two-string problems have this shape: longest common subsequence, the number of distinct subsequences, regular-expression matching, interleaving strings. Name the state as a pair of prefix lengths, then ask what the last characters force.
Complexity. Time O(|a| · |b|) · Space O(|b|)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def edit_distance(a, b):
prev = list(range(len(b) + 1)) # row 0: j insertions
for i in range(1, len(a) + 1):
cur = [i] + [0] * len(b) # column 0: i deletions
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1] # last letters match: no cost
else:
cur[j] = 1 + min(prev[j - 1], # replace
prev[j], # delete from a
cur[j - 1]) # insert into a
prev = cur
return prev[len(b)]#include <string>
#include <vector>
#include <algorithm>
int solve(const std::string& a, const std::string& b) {
const int m = static_cast<int>(b.size());
std::vector<int> prev(m + 1), cur(m + 1);
for (int j = 0; j <= m; ++j) prev[j] = j; // row 0: j insertions
for (int i = 1; i <= static_cast<int>(a.size()); ++i) {
cur[0] = i; // column 0: i deletions
for (int j = 1; j <= m; ++j) {
cur[j] = a[i - 1] == b[j - 1]
? prev[j - 1]
: 1 + std::min({prev[j - 1], prev[j], cur[j - 1]});
}
std::swap(prev, cur);
}
return prev[m];
}class Solution {
public int editDistance(String a, String b) {
int m = b.length();
int[] prev = new int[m + 1], cur = new int[m + 1];
for (int j = 0; j <= m; j++) prev[j] = j; // row 0: j insertions
for (int i = 1; i <= a.length(); i++) {
cur[0] = i; // column 0: i deletions
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) cur[j] = prev[j - 1];
else cur[j] = 1 + Math.min(prev[j - 1], Math.min(prev[j], cur[j - 1]));
}
int[] t = prev; prev = cur; cur = t;
}
return prev[m];
}
}function editDistance(a, b) {
let prev = Array.from({ length: b.length + 1 }, (_, j) => j); // row 0: j insertions
for (let i = 1; i <= a.length; i++) {
const cur = new Array(b.length + 1);
cur[0] = i; // column 0: i deletions
for (let j = 1; j <= b.length; j++) {
cur[j] = a[i - 1] === b[j - 1]
? prev[j - 1] // match: no cost
: 1 + Math.min(prev[j - 1], prev[j], cur[j - 1]); // replace, delete, insert
}
prev = cur;
}
return prev[b.length];
}fn solve(a: &str, b: &str) -> usize {
let (a, b) = (a.as_bytes(), b.as_bytes());
let mut prev: Vec<usize> = (0..=b.len()).collect(); // row 0: j insertions
let mut cur = vec![0usize; b.len() + 1];
for i in 1..=a.len() {
cur[0] = i; // column 0: i deletions
for j in 1..=b.len() {
cur[j] = if a[i - 1] == b[j - 1] {
prev[j - 1]
} else {
1 + prev[j - 1].min(prev[j]).min(cur[j - 1])
};
}
std::mem::swap(&mut prev, &mut cur);
}
prev[b.len()]
}solve :: String -> String -> Int
solve a b = last (foldl step [0 .. length b] a)
where
-- step turns row i-1 into row i for the next character x of a
step prev@(p0 : _) x = scanl cell (p0 + 1) (zip3 b prev (tail prev))
where
cell left (y, diag, up)
| x == y = diag
| otherwise = 1 + minimum [diag, up, left]
step [] _ = []Variants to try
- Recover the operations: walk back from d[|a|][|b|], at each cell taking the neighbour that produced its value.
- Weighted edits, for instance replacements costing 2: change the constants; the recurrence is the same.
- Only insertions and deletions allowed: the distance is |a| + |b| − 2 · LCS(a, b).
- Is the distance at most k? Fill only the diagonal band of width 2k + 1, O(k · n).
Next problems
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem → Medium15 minCount the palindromic substrings
Count every contiguous substring that reads the same backwards, counting different positions separately. Each successful expansion step is one more.
Open the problem →Write a solution and run it against the real test table.
Keep going
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem → Medium15 minCount the palindromic substrings
Count every contiguous substring that reads the same backwards, counting different positions separately. Each successful expansion step is one more.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.