Reconstructing the Answer & the Edit Script
In short: a DP table's final cell only gives a number. To get the actual
answer — which items were kept, inserted or deleted — walk back from that cell
to (0, 0), replaying at each step which neighbour it was built from: a
diagonal match is kept, otherwise the walk goes left (insert) or up (delete)
depending on which neighbour holds the table's value. The walk runs backwards,
so reverse the emitted list at the end. Hirschberg's trick gets the same path
in O(n) space by never keeping the whole table at all.
The survival score says 4 of 5 lines survived, but not which 4, and a history panel that can't show what changed isn't much use. Quarry needs an edit script: an ordered list of keep, delete and insert that turns the old version into the new one.
Every number in a DP table was chosen from a neighbour. Walk those choices backwards from the final cell and you recover the answer itself, not just its size, and with one more idea you can do it without storing the table.
Walking back from the corner
Take the LCS table from lesson 2, for CRATE against TRACE. Start at the
bottom-right cell (i, j) = (5, 5) and repeat until you reach (0, 0):
- If
a[i-1] == b[j-1], that item is kept. Emit=and step diagonally. - Otherwise, if moving left keeps the same value (
table[i][j-1] >= table[i-1][j]), thenb[j-1]was inserted. Emit+and step left. - Otherwise
a[i-1]was deleted. Emit-and step up. - Once
iorjreaches 0, only one direction is left: the remaining items ofbare inserts, or the remaining items ofaare deletes.
The walk emits the script backwards, so reverse it at the end.
Walking back from the corner replays every choice the fill made. Diagonals are kept items, left steps are inserts and up steps are deletes.
Start in the corner, which holds 3. E equals E, so E was kept. Emit = E and step diagonally. 6 by 6 table. At row 5, column 5 — value 3. 36 of 36 cells filled.
The walk visits at most m + n cells, so it costs O(m + n) on top of the fill.
Filling the table is the same O(m · n) time as lesson 2, and keeping the
whole table to walk back over it costs O(m · n) space — the price this
lesson pays for the extra arrows, until Hirschberg's trick below.
The expensive part is keeping the table.
Step through a tiny walk and watch i and j fall:
old, new = ["a", "b"], ["b", "c"]
t = [[0, 0, 0], [0, 0, 0], [0, 1, 1]]
script, i, j = [], 2, 2
while i > 0 or j > 0:
if i > 0 and j > 0 and old[i - 1] == new[j - 1]:
script.append("=" + old[i - 1])
i, j = i - 1, j - 1
elif j > 0 and (i == 0 or t[i][j - 1] >= t[i - 1][j]):
script.append("+" + new[j - 1])
j -= 1
else:
script.append("-" + old[i - 1])
i -= 1
print(script[0])Why ties go left
A replaced line is a delete plus an insert, and both orders are equally short. Which one you get depends only on how you break the tie. Walking backwards and preferring the insert means the insert is emitted first, so after the reverse it comes second. That gives the order every diff reader expects: the old line, then its replacement.
old, new = ["shards=2"], ["shards=4"]
t = [[0, 0], [0, 0]]
out, i, j = [], 1, 1
while i > 0 or j > 0:
if i > 0 and j > 0 and old[i - 1] == new[j - 1]:
out.append("=" + old[i - 1]); i -= 1; j -= 1
elif j > 0 and (i == 0 or t[i][j - 1] >= t[i - 1][j]):
out.append("+" + new[j - 1]); j -= 1
else:
out.append("-" + old[i - 1]); i -= 1
print(out[::-1])Here's a walk with the wrong loop condition:
Turning [a, b] into [b] deletes a, but the script leaves that out because the loop stops as soon as one index hits 0. Make the walk run until both are 0.
Parent pointers: the same idea in one dimension
Lesson 1's table works the same way. Store, for each position, the earlier
position its best run extended (a parent pointer), then follow parents back
from the largest best. That's the warmup exercise: the tails row gives the
length, and parent pointers give the run.
Hirschberg: the path without the table
Two rows are enough for the length, but the walk needs every row, and two 100,000-line files make a table of 10¹⁰ cells. Hirschberg's algorithm recovers the path in linear space by divide and conquer:
- Split
aat its middle row,mid = len(a) // 2. - Run the two-row LCS forward over
a[:mid]againstb. Its last row says, for eachj, how much ofb[:j]the top half can match. - Run it backward over
a[mid:]againstb, both reversed. That says how much ofb[j:]the bottom half can match. - The best path crosses the middle row at the
jwhere the two add up to the most. Take the smallest suchj. - Recurse on the top-left and bottom-right pieces. Neither piece can use the other two quadrants, so they are thrown away.
Hirschberg only ever holds two rows. It finds where the answer path crosses the middle row, discards two quadrants the path can't enter, and recurses on the other two.
Split CRATE after its middle: CR on top, ATE below. The only question is where the path crosses the line between row 2 and row 3. 6 by 6 table. 6 of 36 cells filled.
The two pieces together have half the cells of the rectangle they came from, so each level costs half the one above. Total time stays O(m · n), about twice a single fill, while memory drops to O(n) plus the recursion stack. The total is 1 + ½ + ¼ + …: 1.5 fills after two levels, 1.98 after seven, 1.99 after eight, and never 2. However deep the recursion goes, Hirschberg does at most twice the plain table's work, using two rows of memory.
Your own walk, drawn
Change a and b and run it. Your loop fills the table, then lights up each
cell of the walk back as it emits an operation:
Your own walk, from the corner back to the start. Every lit cell is one operation of the edit script.
Idioms & real-world patterns
Alignments
The same walk over an edit-distance table gives an alignment: both strings
one above the other with - in the gaps, the way spell checkers and gene
comparisons show a difference. The build exercise produces one.
⚡ Advanced: tie rules are part of the contract
Most pairs of versions have several shortest scripts, and tie-breaking alone picks which one you print. Write the rule down and test it, or two implementations of the "same" diff will disagree.
Quick practice
def edit_script(old, new):
m, n = len(old), len(new)
t = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if old[i - 1] == new[j - 1]:
t[i][j] = t[i - 1][j - 1] + 1
else:
t[i][j] = max(t[i - 1][j], t[i][j - 1])
script, i, j = [], m, n
while i > 0 or j > 0:
if i > 0 and j > 0 and old[i - 1] == new[j - 1]:
script.append(["=", old[i - 1]])
i, j = i - 1, j - 1
elif j > 0 and (i == 0 or t[i][j - 1] >= t[i - 1][j]):
script.append(["+", new[j - 1]])
j -= 1
else:
script.append(["-", old[i - 1]])
i -= 1
return script[::-1]
print(edit_script(["p", "q"], ["q", "p"]))x should become y, but this inserts another x instead. Fix the insert branch to read from new.
🎯 Your turn
Write edit_script(old, new). Both are lists of lines. Return the edit script
as a list of [op, line] pairs, where op is "=" (kept), "-" (deleted from
old) or "+" (inserted from new). Keep as many lines as possible (an LCS).
Build the full LCS table and walk back from the corner with the rule from this
lesson: a match goes diagonal; otherwise go left (insert) when
table[i][j-1] >= table[i-1][j], else up (delete). Reverse at the end.
edit_script(["a", "x", "c"], ["a", "y", "c"])→[["=", "a"], ["-", "x"], ["+", "y"], ["=", "c"]]edit_script([], ["new"])→[["+", "new"]]
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green means this piece of the app is built. ✅