Edit distance

THE PROBLEM

“A text tool compares a source string with a target. One operation inserts, deletes, or replaces one character, each costing one. Return the minimum number of operations. Explain which prefixes your state describes before optimizing its memory.”

Write this:

def edit_distance(source, target):
    ...

Constructed practice question. Prerequisite: DP. Levenshtein distance counts these three operations; adjacent transposition is not a separate permitted operation. Python strings here are sequences of Unicode code points, which may differ from user-perceived characters.

Contract	Required behavior
Input	Two strings, compared case-sensitively by code point
Output	Minimum unit-cost insertion/deletion/replacement count
Boundaries	Equal strings cost 0; empty versus length n costs n
Failure	Nonstrings raise `ValueError`
Scope	Distance only; no edit script, normalization, transposition, or weighted costs

Optional refresher · the underlying tool

Edit distance asks the fewest insertions, deletions, or substitutions that transform one string into another. A DP cell dp[i][j] summarizes the first i source and first j target characters:

source, target = "cat", "cut"
same = source[1] == target[1]   # False: a vs u
substitution_cost = 0 if same else 1

"cat" → "cut" needs one substitution. Empty source to "cut" needs three insertions; those empty-prefix cells are base cases, not special patches at the end.

A design choice worth saying aloud

Let distance[i][j] mean the cost for two prefixes, rather than an unexplained cell number. Initialize the empty-prefix row and column from insertion/deletion costs; every other cell refers to smaller prefixes. If memory is optimized to two rows, preserve which row means i - 1 before overwriting it.

What the interviewer expects

The interviewer gives you the scenario and the contract above. Explain what a successful call returns, walk through one example below, and name what your state means before choosing a data structure.

Done means: Minimum unit-cost insertion/deletion/replacement count.

Now predict each output before looking at the reference; invalid input should leave any existing state unchanged unless the contract says otherwise.

Test-case scenarios to settle before coding

01 · Representative

Input / starting state: "kitten" to "sitting"
Expected result: 3

What it is testing: Replace, replace, insert is optimal.

02 · Equal

Input / starting state: same string twice
Expected result: 0

What it is testing: No operation is required.

03 · Empty side

Input / starting state: "" to length-n text
Expected result: n

What it is testing: Every target symbol must be inserted.

04 · Order

Input / starting state: "ab" to "ba"
Expected result: 2

What it is testing: Transposition is not a baseline operation.

05 · Unicode

Input / starting state: strings compared by Python code point
Expected result: distance over exact code points

What it is testing: No implicit normalization/grapheme logic.

06 · Invalid

Input / starting state: either input non-string
Expected result: ValueError

What it is testing: The API does not stringify values.

For each case, show which branch or state change produces that result.

kitten → sitting costs 3: replace k→s, replace e→i, append g. ab → ba costs 2, not 1, because swapping is excluded. A list of characters raises ValueError rather than silently changing the input contract. Ask whether an actual edit script or only a threshold decision is required; both affect retained state.

Diagram: Test-case scenarios to settle before coding

Before reading the answer, fill the boundary row and column for cat → cut. Explain why D(0,j)=j is a sequence of real operations rather than a magic constant.

Solution, prefix recurrence, and follow-ups

The baseline branches recursively over insertion, deletion, and replacement. Many branches revisit the same pair of remaining suffixes; without memoization, work grows exponentially. A full DP table removes that repetition and makes the state meaning inspectable before any rolling-row optimization.

Let D(i,j) be the minimum cost to convert the first i source characters into the first j target characters. The final operation either deletes the final source character, inserts the final target character, or aligns those two characters with zero/matching or one/replacement cost. Take the minimum of the three pictured predecessors. Boundary cells consume or produce all characters of one prefix.

when computing cell (i,j), its upper, left, and diagonal predecessors already contain optimal prefix costs. Every edit script has one of these final actions, and every predecessor plus that action is a valid script. This establishes both a lower bound and a construction attaining the recurrence.

Source prefix / target prefix	empty	c	cu	cut
empty	0	1	2	3
c	1	0	1	2
ca	2	1	1	2
cat	3	2	2	1

Only the previous row and current row are needed for distance. Put the shorter string on columns, using symmetry of unit costs. For lengths m,n, time is O(mn) when both are nonempty, or more generally O((m+1)(n+1)); auxiliary space is O(min(m,n)+1). Rows are numeric costs, and the returned integer needs constant word-model output space. Swapping inputs would need reconsideration if insertion and deletion had different costs.

Follow the three candidate costs into the first focused cell, then watch the frontier and two-row memory band advance. The full grid preserves teaching history.

Edit-distance predecessor costs arrive before the cell commits and the frontier advances

Follow-up 1 — return an edit script. Predict which information rolling rows discard. Preserve a full table or backpointers and walk from (m,n) to (0,0). Specify deterministic tie handling. A divide-and-conquer reconstruction can reduce memory, but it requires additional reasoning rather than reading discarded cells.

Follow-up 2 — only accept distance ≤k. If lengths differ by more than k, reject immediately. Restrict computation to a diagonal band and cap costs above k, carefully representing cells outside the band as unreachable. This is useful when k is small; it is not a general shortcut for an unrestricted exact distance.

Senior depth derives state/boundaries and verifies an independent recursive oracle. Lead depth clarifies Unicode normalization and user-visible edit semantics.

Reference: solution.py (download file, source below); tests cover all short binary strings, symmetry, empty inputs, transposition exclusion, and code-point behavior.

solution.py · solution.py

"""Unit-cost Levenshtein distance with one rolling row."""


def edit_distance(source, target):
    if not isinstance(source, str) or not isinstance(target, str):
        raise ValueError("string inputs required")
    if len(source) < len(target):
        source, target = target, source
    previous = list(range(len(target) + 1))
    for i, a in enumerate(source, 1):
        current = [i]
        for j, b in enumerate(target, 1):
            current.append(min(previous[j] + 1,
                               current[j - 1] + 1,
                               previous[j - 1] + (a != b)))
        previous = current
    return previous[-1]

python -m unittest discover -s curriculum/01-code/02-data-structures-algorithms/problems/35-edit-distance -p 'test_*.py'