These are the notes for DSA episode 68. On the metro you type "reachng home by 7" to the family group, and the phone suggests reaching, not teaching. Why? reaching is one edit away (insert i), teaching is two (replace r with t, insert i). The fewest one-letter edits that turn one word into another is the edit distance. We write the obvious recursion (correct, but Time Limit Exceeded on 24 vs 21 letters), see why it is slow, and build the table dp[i][j] from three neighbours: the diagonal (replace), the cell above (delete) and the cell to the left (insert). Then we print the actual edits, shrink the table to two rows, and run three real bugs. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).
The problem, in real life
| Autocorrect on your phone | In code |
|---|---|
The word you typed (reachng) |
string a |
A dictionary word (reaching) |
string b |
| Add a missing letter | insert |
| Remove an extra letter | delete |
| Fix a wrong letter | replace |
| Fewest fixes | the edit distance |
| Suggest the closest word | smallest edit distance wins |
Every word, from zero
- String: a sequence of characters, like
"horse". - Prefix: the first few letters of a string. The prefixes of
"tea"are"","t","te","tea". - Edit (operation): one change to one letter: insert a letter, delete a letter, or replace a letter with another.
- Edit distance (Levenshtein distance): the fewest edits that turn string
ainto stringb. Named after Vladimir Levenshtein, who described it in 1965. - Recursion: a function that calls itself on a smaller problem.
- Overlapping sub-problems: the same smaller question is asked again and again (like Fibonacci in episode 62).
- State: the few numbers that fully describe a sub-problem; here
(i, j): the firstiletters ofaand the firstjletters ofb. - Recurrence: the rule that builds a cell from smaller cells.
- Tabulation (bottom-up DP): filling a table from the smallest sub-problems up.
- Walk back (backtracking the table): starting from the answer cell and following which neighbour each value came from, to recover the actual choices.
- Rolling array: keeping only the rows the next row needs (here two).
- LCS (longest common subsequence): episode 67; the same table, with only inserts and deletes.
Problem statement
Given two strings a and b, return the minimum number of operations to convert a into b. Allowed operations: insert a character, delete a character, replace a character. (LeetCode 72, Edit Distance, Hard.)
| a | b | Answer | One best list of edits |
|---|---|---|---|
horse |
ros |
3 |
replace h→r (rorse), delete r (rose), delete e (ros) |
intention |
execution |
5 |
replace i→e, n→x, t→e, e→c, n→u |
kitten |
sitting |
3 |
k→s, e→i, insert g |
"" |
chai |
4 |
insert all four letters |
tea |
"" |
3 |
delete all three letters |
code |
code |
0 |
nothing to do |
Constraints: 0 ≤ a.length, b.length ≤ 500, lowercase English letters.
Obvious correct idea: try all three edits
i points into a, j into b. If one string is used up, the rest of the other must be inserted or deleted. If the letters match, move both pointers for free. Otherwise try insert (j + 1), delete (i + 1) and replace (i + 1, j + 1), each costing 1, and keep the cheapest.
import java.util.*;
public class Main {
static int editDistance(String a, String b) {
return go(a, b, 0, 0);
}
static int go(String a, String b, int i, int j) {
if (i == a.length()) return b.length() - j;
if (j == b.length()) return a.length() - i;
if (a.charAt(i) == b.charAt(j)) return go(a, b, i + 1, j + 1);
int ins = go(a, b, i, j + 1);
int del = go(a, b, i + 1, j);
int rep = go(a, b, i + 1, j + 1);
return 1 + Math.min(ins, Math.min(del, rep));
}
public static void main(String[] args) {
System.out.println(editDistance("horse", "ros"));
System.out.println(editDistance("intention", "execution"));
System.out.println(editDistance("kitten", "sitting"));
System.out.println(editDistance("", "chai"));
System.out.println(editDistance("tea", ""));
System.out.println(editDistance("code", "code"));
}
}
3
5
3
4
3
0
All correct. Now 24 letters against 21:
import java.util.*;
public class Main {
static int editDistance(String a, String b) {
return go(a, b, 0, 0);
}
static int go(String a, String b, int i, int j) {
if (i == a.length()) return b.length() - j;
if (j == b.length()) return a.length() - i;
if (a.charAt(i) == b.charAt(j)) return go(a, b, i + 1, j + 1);
int ins = go(a, b, i, j + 1);
int del = go(a, b, i + 1, j);
int rep = go(a, b, i + 1, j + 1);
return 1 + Math.min(ins, Math.min(del, rep));
}
public static void main(String[] args) {
String a = "kitten".repeat(4), b = "sitting".repeat(3);
long t0 = System.nanoTime();
int d = editDistance(a, b);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("24 vs 21 letters: " + d + ", " + ms + " ms");
}
}
Time Limit Exceeded (no output after 25 seconds)
Why is it slow?
Every mismatch splits into three calls, so the work grows like 3^(n + m). But a call depends on just two numbers, (i, j). Replace once, or insert then delete: both reach (i + 1, j + 1). The same pair is solved again and again, and there are only (n + 1) × (m + 1) different pairs: 25 × 22 = 550 here, not trillions.
The key insight: three neighbours
State: dp[i][j] = the fewest edits to turn the first i letters of a into the first j letters of b.
Base: dp[0][j] = j (insert j letters into an empty string), dp[i][0] = i (delete all i letters).
Recurrence: look at the last letters, a[i - 1] and b[j - 1].
| Case | Value | Meaning |
|---|---|---|
| Same letter | dp[i - 1][j - 1] |
keep it, free (the diagonal) |
| Different: replace | 1 + dp[i - 1][j - 1] |
change a[i-1] into b[j-1] ↖ |
| Different: delete | 1 + dp[i - 1][j] |
remove a[i-1], then match the rest ↑ |
| Different: insert | 1 + dp[i][j - 1] |
add b[j-1] at the end ← |
When the letters differ, take 1 + the smallest of the three. Answer: dp[n][m].
By hand: tea → eat
Rows are prefixes of tea, columns are prefixes of eat.
| a ↓ b → | "" |
e |
ea |
eat |
|---|---|---|---|---|
"" |
0 | 1 | 2 | 3 |
t |
1 | 1 | 2 | 2 |
te |
2 | 1 | 2 | 3 |
tea |
3 | 2 | 1 | 2 |
t → e: different,1 + min(0, 1, 1) = 1(replace).t → eat: last letters botht, copy the diagonalt → ea= 2.te → e: last letters bothe, copy the diagonalt → ""= 1.tea → eat:a ≠ t,1 + min(replace 2, delete 3, insert 1) = 2.- Walk back: insert
tat the end, keepaande, delete the firstt: tea → ea → eat.
Solution in Java: the 2D table
import java.util.*;
public class Main {
static int editDistance(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;
for (int j = 0; j <= m; j++) dp[0][j] = j;
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 {
int rep = dp[i - 1][j - 1], del = dp[i - 1][j], ins = dp[i][j - 1];
dp[i][j] = 1 + Math.min(rep, Math.min(del, ins));
}
}
return dp[n][m];
}
public static void main(String[] args) {
System.out.println(editDistance("horse", "ros"));
System.out.println(editDistance("intention", "execution"));
System.out.println(editDistance("kitten", "sitting"));
System.out.println(editDistance("", "chai"));
System.out.println(editDistance("tea", ""));
System.out.println(editDistance("code", "code"));
}
}
3
5
3
4
3
0
The 24-letter strings that timed out, and two 3,000-letter strings (9 million cells):
import java.util.*;
public class Main {
static int editDistance(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;
for (int j = 0; j <= m; j++) dp[0][j] = j;
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 {
int rep = dp[i - 1][j - 1], del = dp[i - 1][j], ins = dp[i][j - 1];
dp[i][j] = 1 + Math.min(rep, Math.min(del, ins));
}
}
return dp[n][m];
}
public static void main(String[] args) {
String a = "kitten".repeat(4), b = "sitting".repeat(3);
long t0 = System.nanoTime();
int d = editDistance(a, b);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("24 vs 21 letters: " + d + ", " + ms + " ms");
StringBuilder x = new StringBuilder(), y = new StringBuilder();
for (int i = 0; i < 3000; i++) {
x.append((char) ('a' + i * 7 % 26));
y.append((char) ('a' + i * 11 % 26));
}
long t1 = System.nanoTime();
int d2 = editDistance(x.toString(), y.toString());
long ms2 = (System.nanoTime() - t1) / 1000000;
System.out.println("3000 vs 3000 letters: " + d2 + ", " + ms2 + " ms");
}
}
24 vs 21 letters: 14, 1 ms
3000 vs 3000 letters: 2769, 79 ms
The actual edits: walk the table back
From dp[n][m]: if the letters match, step diagonally for free; else if the value came from the diagonal + 1 it was a replace, from above + 1 a delete, otherwise from the left + 1 an insert. The edits come out last-first, so reverse the list.
import java.util.*;
public class Main {
static void steps(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;
for (int j = 0; j <= m; j++) dp[0][j] = j;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; 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]));
List<String> ops = new ArrayList<>();
int i = n, j = m;
while (i > 0 || j > 0) {
if (i > 0 && j > 0 && a.charAt(i - 1) == b.charAt(j - 1)) {
i--; j--;
} else if (i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + 1) {
ops.add("replace " + a.charAt(i - 1) + " with " + b.charAt(j - 1));
i--; j--;
} else if (i > 0 && dp[i][j] == dp[i - 1][j] + 1) {
ops.add("delete " + a.charAt(i - 1)); i--;
} else {
ops.add("insert " + b.charAt(j - 1)); j--;
}
}
Collections.reverse(ops);
System.out.println(a + " -> " + b + ": " + dp[n][m] + " " + ops);
}
public static void main(String[] args) {
steps("horse", "ros");
steps("tea", "eat");
steps("intention", "execution");
steps("reachng", "reaching");
steps("reachng", "teaching");
}
}
horse -> ros: 3 [replace h with r, delete r, delete e]
tea -> eat: 2 [delete t, insert t]
intention -> execution: 5 [replace i with e, replace n with x, replace t with e, replace e with c, replace n with u]
reachng -> reaching: 1 [insert i]
reachng -> teaching: 2 [replace r with t, insert i]
There can be several best lists: LeetCode's explanation of intention → execution uses a delete and an insert; the walk back above finds five replacements. Both cost 5.
Two rows: O(m) space
A cell reads the diagonal and the cell above (previous row) and the cell to the left (its own row), so two rows are enough: prev and cur. Set cur[0] = i at the start of every row (the base column), and swap after each row; the finished last row ends up in prev.
import java.util.*;
public class Main {
static int editDistance(String a, String b) {
int n = a.length(), m = b.length();
int[] prev = new int[m + 1], cur = new int[m + 1];
for (int j = 0; j <= m; j++) prev[j] = j;
for (int i = 1; i <= n; i++) {
cur[0] = i;
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];
}
public static void main(String[] args) {
System.out.println(editDistance("horse", "ros"));
System.out.println(editDistance("intention", "execution"));
System.out.println(editDistance("kitten", "sitting"));
System.out.println(editDistance("", "chai"));
System.out.println(editDistance("tea", ""));
System.out.println(editDistance("code", "code"));
StringBuilder x = new StringBuilder(), y = new StringBuilder();
for (int i = 0; i < 3000; i++) {
x.append((char) ('a' + i * 7 % 26));
y.append((char) ('a' + i * 11 % 26));
}
long t1 = System.nanoTime();
int d2 = editDistance(x.toString(), y.toString());
long ms2 = (System.nanoTime() - t1) / 1000000;
System.out.println("3000 vs 3000 letters: " + d2 + ", " + ms2 + " ms");
}
}
3
5
3
4
3
0
3000 vs 3000 letters: 2769, 34 ms
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
// Edit distance (LeetCode 72): two rows, prev = row i - 1, cur = row i.
int editDistance(const string& a, const string& b) {
int n = a.size(), m = b.size();
vector<int> prev(m + 1), cur(m + 1);
for (int j = 0; j <= m; j++) prev[j] = j; // "" -> first j letters: j inserts
for (int i = 1; i <= n; i++) {
cur[0] = i; // first i letters -> "": i deletes
for (int j = 1; j <= m; j++) {
if (a[i - 1] == b[j - 1]) cur[j] = prev[j - 1]; // same letter: free
else cur[j] = 1 + min({prev[j - 1], prev[j], cur[j - 1]}); // replace, delete, insert
}
swap(prev, cur);
}
return prev[m];
}
int main() {
cout << editDistance("horse", "ros") << "\n";
cout << editDistance("intention", "execution") << "\n";
cout << editDistance("kitten", "sitting") << "\n";
cout << editDistance("", "chai") << "\n";
cout << editDistance("tea", "") << "\n";
cout << editDistance("code", "code") << "\n";
string x, y;
for (int i = 0; i < 3000; i++) { x += char('a' + i * 7 % 26); y += char('a' + i * 11 % 26); }
cout << editDistance(x, y) << "\n";
}
3
5
3
4
3
0
2769
The same solution in Python
# Edit distance (LeetCode 72): two rows, prev = row i - 1, cur = row i.
def edit_distance(a, b):
n, m = len(a), len(b)
prev = list(range(m + 1)) # "" -> first j letters: j inserts
for i in range(1, n + 1):
cur = [i] + [0] * m # first i letters -> "": i deletes
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1] # same letter: free
else:
cur[j] = 1 + min(prev[j - 1], prev[j], cur[j - 1]) # replace, delete, insert
prev = cur
return prev[m]
print(edit_distance("horse", "ros"))
print(edit_distance("intention", "execution"))
print(edit_distance("kitten", "sitting"))
print(edit_distance("", "chai"))
print(edit_distance("tea", ""))
print(edit_distance("code", "code"))
x = "".join(chr(ord("a") + i * 7 % 26) for i in range(3000))
y = "".join(chr(ord("a") + i * 11 % 26) for i in range(3000))
print(edit_distance(x, y))
3
5
3
4
3
0
2769
Three real bugs
Bug 1: the base row and column left at 0. Java fills a new array with zeros, so deleting or inserting the first letters looks free.
import java.util.*;
public class Main {
static int editDistance(String a, String b) {
int n = a.length(), m = b.length();
int[][] dp = new int[n + 1][m + 1];
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 {
int rep = dp[i - 1][j - 1], del = dp[i - 1][j], ins = dp[i][j - 1];
dp[i][j] = 1 + Math.min(rep, Math.min(del, ins));
}
}
return dp[n][m];
}
public static void main(String[] args) {
System.out.println(editDistance("", "chai"));
System.out.println(editDistance("horse", "ros"));
}
}
0
2
0 instead of 4, and 2 instead of 3. Fix: dp[i][0] = i and dp[0][j] = j.
Bug 2: the + 1 forgotten.
import java.util.*;
public class Main {
static int editDistance(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;
for (int j = 0; j <= m; j++) dp[0][j] = j;
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 {
int rep = dp[i - 1][j - 1], del = dp[i - 1][j], ins = dp[i][j - 1];
dp[i][j] = Math.min(rep, Math.min(del, ins));
}
}
return dp[n][m];
}
public static void main(String[] args) {
System.out.println(editDistance("horse", "ros"));
System.out.println(editDistance("intention", "execution"));
System.out.println(editDistance("kitten", "sitting"));
}
}
0
0
0
Every edit became free, so every pair of words is 0 edits apart. No error, just wrong. Fix: dp[i][j] = 1 + Math.min(...).
Bug 3: the table one row short.
import java.util.*;
public class Main {
static int editDistance(String a, String b) {
int n = a.length(), m = b.length();
int[][] dp = new int[n][m + 1];
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;
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 {
int rep = dp[i - 1][j - 1], del = dp[i - 1][j], ins = dp[i][j - 1];
dp[i][j] = 1 + Math.min(rep, Math.min(del, ins));
}
}
return dp[n][m];
}
public static void main(String[] args) {
System.out.println(editDistance("horse", "ros"));
}
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
at Main.editDistance(Main.java:7)
at Main.main(Main.java:21)
Prefix lengths go from 0 to n: that is n + 1 rows (and m + 1 columns).
Complexity
| Approach | Time | Space | Big input |
|---|---|---|---|
| Try every edit (recursion) | about O(3^(n + m)) | O(n + m) stack | 24 vs 21 letters: Time Limit Exceeded |
| DP table (2D) | O(n × m) | O(n × m) | 3,000 × 3,000: well under a second |
| Two rows | O(n × m) | O(m) | same answers |
For LeetCode's limit (500 × 500) that is 250,000 cells: instant.
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| No base row and column | 0 instead of 4; 2 instead of 3 |
empty prefixes cost letters | dp[i][0] = i, dp[0][j] = j |
min(rep, del, ins) without + 1 |
0 for every pair |
edits became free | 1 + min(...) |
new int[n][m + 1] |
ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5 |
prefix lengths 0 … n |
n + 1 rows, m + 1 columns |
Two rows, no cur[0] = i |
wrong answers after the first row | base column lost | set cur[0] every row |
a.charAt(i) instead of a.charAt(i - 1) in the table |
wrong answers / StringIndexOutOfBoundsException |
row i means the first i letters |
last letter is i - 1 |
| Mixing up insert and delete in the walk back | wrong edit list | ↑ = delete from a, ← = insert from b |
label the moves once and stick to them |
Mini project: a tiny autocorrect
Keep a small dictionary (reaching, teaching, train, station, tomorrow, please). For every word the user types, compute the edit distance to each dictionary word and suggest the closest one (ties: the first in the list); if the distance is 0, the word is correct. Extension: print the edits with the walk back, and only suggest when the distance is at most 2.
Practice
1. Edit Distance (LeetCode 72). The episode's problem: submit the two-row version.
2. Delete Operation for Two Strings (LeetCode 583). Only deletes are allowed, from either string. Fewest deletes to make them equal?
Solution
The same table without replace: a mismatch costs 1 + min(up, left). (Equivalently n + m - 2 × LCS, episode 67.)
# Delete Operation for Two Strings (LeetCode 583): only deletes, so the answer is n + m - 2 * LCS.
def min_distance(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i
for j in range(m + 1):
dp[0][j] = j
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]) # delete from a, or from b
return dp[n][m]
print(min_distance("sea", "eat"), min_distance("leetcode", "etco"))
2 4
3. One Edit Distance (LeetCode 161). Are two strings exactly one edit apart? Do it in O(n) without a table.
Solution
Walk until the first mismatch; then the rest must match after skipping one letter in the longer string (insert) or in both (replace).
# One Edit Distance (LeetCode 161): exactly one edit apart? O(n) time, no table.
def is_one_edit(s, t):
if len(s) > len(t):
s, t = t, s
if len(t) - len(s) > 1:
return False
for i in range(len(s)):
if s[i] != t[i]:
if len(s) == len(t):
return s[i + 1:] == t[i + 1:] # replace
return s[i:] == t[i + 1:] # insert into s
return len(t) - len(s) == 1 # one extra letter at the end
print(is_one_edit("ab", "acb"), is_one_edit("cab", "ad"), is_one_edit("1203", "1213"), is_one_edit("a", "a"))
True False True False
4. Minimum ASCII Delete Sum for Two Strings (LeetCode 712). Deletes only, and each delete costs the letter's ASCII code.
Solution
The LeetCode 583 table with weights: the base row and column add up ASCII codes, and a mismatch costs the cheaper deleted letter plus the neighbour.
# Minimum ASCII Delete Sum (LeetCode 712): deletes only, each delete costs the letter's ASCII code.
def minimum_delete_sum(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
dp[i][0] = dp[i - 1][0] + ord(a[i - 1])
for j in range(1, m + 1):
dp[0][j] = dp[0][j - 1] + ord(b[j - 1])
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j] + ord(a[i - 1]), dp[i][j - 1] + ord(b[j - 1]))
return dp[n][m]
print(minimum_delete_sum("sea", "eat"), minimum_delete_sum("delete", "leet"))
231 403
Quick quiz
Turn sunday into saturday. Fewest edits? A) 2 B) 3 C) 4 D) 5
Answer
B) 3: insert a, insert t, replace n with r: sunday → saunday → satunday → saturday.
Interview questions
- State and recurrence?
dp[i][j]= fewest edits from the firstiletters ofato the firstjofb; same last letter:dp[i-1][j-1], else1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]). - Which neighbour is which edit? Diagonal = replace, up = delete from
a, left = insert intoa. - Base cases?
dp[0][j] = j,dp[i][0] = i. - Complexity, and can you save space? O(n × m) time; O(m) space with two rows (or one row plus a saved diagonal).
- How do you print the edits? Keep the full table and walk back from
dp[n][m]. - How is it related to LCS? With only inserts and deletes, the distance is
n + m - 2 × LCS. - Where is it used? Spell check, autocorrect, "did you mean", DNA sequence alignment, fuzzy search.
Glossary
| Term | Meaning |
|---|---|
| Edit distance | Fewest inserts, deletes and replaces to turn a into b |
| Levenshtein distance | Another name for edit distance (V. Levenshtein, 1965) |
| Insert / delete / replace | Add a letter / remove a letter / change a letter |
| Prefix | The first few letters of a string, from "" to the whole string |
| State | (i, j): the first i letters of a, the first j of b |
| Recurrence | Same letter: diagonal; else 1 + min of three neighbours |
| Base case | dp[0][j] = j, dp[i][0] = i |
| Overlapping sub-problems | The same (i, j) reached by different orders of edits |
| Tabulation | Filling the table bottom-up |
| Walk back | Following the table from the answer cell to recover the edits |
| Rolling array | Two rows (prev, cur) instead of the whole table |
| LCS | Longest common subsequence (episode 67) |
Summary
- Edit distance: the fewest one-letter inserts, deletes and replaces from
atob; autocorrect suggests the closest word. - The recursion is correct but about
3^(n + m); only(n + 1) × (m + 1)states exist. dp[i][j]: same last letter → diagonal; else1 + min(↖ replace, ↑ delete, ← insert). Base row and column count letters. Answerdp[n][m].- Walk back for the edits; two rows for
O(m)space. O(n × m)time. Next episode: grid DP, unique paths and minimum path sum.