SyntaxPilot
Courses/DSA and Coding Problems/Lesson 68
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 68 of 90

Edit distance (hard)

queued

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 a into string b. 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 first i letters of a and the first j letters of b.
  • 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 both t, copy the diagonal t → ea = 2.
  • te → e: last letters both e, copy the diagonal t → "" = 1.
  • tea → eat: a ≠ t, 1 + min(replace 2, delete 3, insert 1) = 2.
  • Walk back: insert t at the end, keep a and e, delete the first t: 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

  1. State and recurrence? dp[i][j] = fewest edits from the first i letters of a to the first j of b; same last letter: dp[i-1][j-1], else 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
  2. Which neighbour is which edit? Diagonal = replace, up = delete from a, left = insert into a.
  3. Base cases? dp[0][j] = j, dp[i][0] = i.
  4. Complexity, and can you save space? O(n × m) time; O(m) space with two rows (or one row plus a saved diagonal).
  5. How do you print the edits? Keep the full table and walk back from dp[n][m].
  6. How is it related to LCS? With only inserts and deletes, the distance is n + m - 2 × LCS.
  7. 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 a to b; 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; else 1 + min(↖ replace, ↑ delete, ← insert). Base row and column count letters. Answer dp[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.