Fewest edits to turn one word into another

Dynamic programming Senior Python 3.13+ Kotlin 2.4+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

src, dst = "cat", "cut"
row = list(range(len(dst) + 1))
for i, a in enumerate(src, 1):
    nxt = [i]
    for j, b in enumerate(dst, 1):
        if a == b:
            nxt.append(row[j - 1])
        else:
            nxt.append(1 + min(row[j], nxt[j - 1], row[j - 1]))
    row = nxt
print(row)

Options[3, 2, 2, 1][3, 2, 1, 1][0, 1, 2, 3]

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [3, 2, 2, 1]

Right: the last cell is 1, one replacement (a to u).

Keeping only one previous row gives the same answer as the full table while using memory for one row.

Why not the others?

B [3, 2, 1, 1]. The 'cu' column against 'cat' costs 2.
C [0, 1, 2, 3]. That is the first row before any letters of the source.

The fewest-edits table filled cell by cell, each cell showing which neighbour it came from, for horse to ros and cat to cut.

Steps come from running the Python solution.

Text version

horse to ros:

horse to ros: finished table
Row	∅	r	o	s
∅	0	1	2	3
h	1	1	2	3
o	2	2	1	2
r	3	2	2	2
s	4	3	3	2
e	5	4	4	3

Answer: 3 in cell (e, s), from (s, s).

cat to cut:

cat to cut: finished table
Row	∅	c	u	t
∅	0	1	2	3
c	1	0	1	2
a	2	1	1	2
t	3	2	2	1

Answer: 1 in cell (t, t), from (a, u).

30-second answer

Let cost[i][j] be the edits needed to turn the first i letters of the source into the first j letters of the target. Empty prefixes cost i + j. If the current letters match, cost[i][j] = cost[i - 1][j - 1]; otherwise it is 1 plus the cheapest of delete (up), insert (left) or replace (diagonal). Fill row by row: O(m × n) time and O(m × n) memory for the full table, as here; keeping only two rows cuts memory to O(n) when you need just the number.

Practise saying it · 60 s. No recording, just a timer

Explain the fewest-edits table.

Say your answer out loud, then check which of these points you covered:

cost over prefixes
Match: diagonal; else 1 + min of three
O(m × n)

Deep dive

This is the template for two-string DP: a table over prefixes.

Each move in the table is one kind of edit, which makes the recurrence easy to explain.

Walking back from the last cell recovers the actual edits.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

def fewest_edits(src: str, dst: str) -> int:
    # cost[i][j]: edits to turn src[:i] into dst[:j]
    cost = [[i + j if i == 0 or j == 0 else 0
             for j in range(len(dst) + 1)] for i in range(len(src) + 1)]
    for i, a in enumerate(src, 1):
        for j, b in enumerate(dst, 1):
            if a == b:
                cost[i][j] = cost[i - 1][j - 1]  # letters match: free
            else:
                cost[i][j] = 1 + min(cost[i - 1][j],  # delete a
                                     cost[i][j - 1],  # insert b
                                     cost[i - 1][j - 1])  # swap a for b
    return cost[-1][-1]

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1

Kotlin 2.4

fun fewestEdits(src: String, dst: String): Int {
    // cost[i][j]: edits to turn src[:i] into dst[:j]
    val cost = Array(src.length + 1) { i ->
        IntArray(dst.length + 1) { j ->
            if (i == 0 || j == 0) i + j else 0
        }
    }
    for (i in 1..src.length) {
        for (j in 1..dst.length) {
            cost[i][j] = if (src[i - 1] == dst[j - 1]) {
                cost[i - 1][j - 1] // letters match: free
            } else {
                val swap = cost[i - 1][j - 1]
                1 + minOf(cost[i - 1][j], cost[i][j - 1], swap)
            }
        }
    }
    return cost[src.length][dst.length]
}

Common mistakes

Off-by-one between table indexes and string indexes.
Forgetting the first row and column (edits against an empty prefix).

Senior take & follow-ups

Name what each of the three neighbours means before filling a cell.

Follow-up questions

Think of your answer first, then open the hint.

How do you get O(n) memory?
Show hint
Keep the previous row and the current row only.
How do text diff tools relate?
Show hint
They solve a close cousin (longest common subsequence) and print the insertions and deletions it implies.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.