Edit Distance

MEDIUM✓ CHIP-TIMEDLC #72 — FULL STATEMENT ↗

The drill: Find the fewest single-character insertions, deletions, and substitutions needed to turn one word into another.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two words show up, and the job is finding the smallest number of single-character edits — inserting a letter, deleting a letter, or swapping one letter for another — that turns the first word into the second.

Each edit touches exactly one character and counts as one step regardless of which of the three operations it is. Matching characters that already line up cost nothing and never need to be touched.

Either word can be empty, and letters may repeat freely within or across the two words — the only thing being measured is the shortest chain of edits that bridges them.

EX 01

word1 = "flower" · word2 = "flow"

→ 2

THE BOARD'S EXAMPLE — TWO TRAILING DELETIONS

EX 02

word1 = "abcdef" · word2 = "azced"

→ 3

EX 03

word1 = "" · word2 = ""

→ 0

TWO EMPTY WORDS

either word may be empty; an empty word costs its partner's full length to reach
words hold ordinary letters, lengths staying in the low thousands at most
insert, delete, and substitute each cost exactly one edit — no partial credit
the answer is the single smallest edit count, not the edit sequence itself

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Compare the two words from their last characters backward. If those two characters already match, that pair costs nothing — the problem reduces to the same question on both words with that character stripped off.

HINT 2 THE STRUCTURE

When the last characters differ, exactly one edit has to happen at that position — but which one? Try all three: delete from the first word, insert to match the second, or substitute it, and recurse on whichever leftover pair results.

HINT 3 ONE STEP FROM THE ANSWER

dp(i, j) = dp(i−1, j−1) when word1[i−1] == word2[j−1]; otherwise 1 + min(dp(i−1, j), dp(i, j−1), dp(i−1, j−1)) — deletion, insertion, substitution. Base cases: dp(i, 0) = i, dp(0, j) = j.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE EDIT LEDGERPATTERN · EDIT DISTANCE TABLEword1 = "ab" · word2 = "ba"

STEP 1

word1='ab', word2='ba'. Base cases: dp[0][j]=j inserts build word2's prefix from nothing; dp[i][0]=i deletes empty word1's prefix.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/edit-distance.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)
        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 word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

        return dp[n][m]

TIME O(M·N)SPACE O(M·N)PYTHON · RACE PACE · 17 LN

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        def rec(i, j):
            if i == 0:
                return j
            if j == 0:
                return i
            if word1[i - 1] == word2[j - 1]:
                return rec(i - 1, j - 1)
            return 1 + min(
                rec(i - 1, j),      # delete from word1
                rec(i, j - 1),      # insert into word1
                rec(i - 1, j - 1),  # substitute
            )

        return rec(len(word1), len(word2))

TIME O(3ⁿ)SPACE O(N)PYTHON · TRAINING PACE · 16 LN

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.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 (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                }
            }
        }
        return dp[n][m];
    }
}

TIME O(M·N)SPACE O(M·N)JAVA · RACE PACE · 19 LN

class Solution {
    private String word1, word2;

    public int minDistance(String word1, String word2) {
        this.word1 = word1;
        this.word2 = word2;
        return rec(word1.length(), word2.length());
    }

    private int rec(int i, int j) {
        if (i == 0) return j;
        if (j == 0) return i;
        if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
            return rec(i - 1, j - 1);
        }
        return 1 + Math.min(rec(i - 1, j), Math.min(rec(i, j - 1), rec(i - 1, j - 1)));
    }
}

TIME O(3ⁿ)SPACE O(N)JAVA · TRAINING PACE · 18 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED