Edit Distance

mediumTests passed 2026-11-11v1.0.0

TC: O(M * N)|SC: O(N)

2D DP Strings Original Statement (leetcode).md

1. Core Invariant / The Trick

Levenshtein recurrence on rolling 1D row: if `w1[i] == w2[j]`, inherit `diag`; otherwise `1 + min(dp[j] /*delete*/, dp[j-1] /*insert*/, diag /*replace*/)`. Remember `dp[0] = i` on each row start.

2. Complexity Bounds & Proof

Evaluates all prefix edit pairs `(i, j)` updating a single row plus scalar `diag` backup.

3. Minimal Idiomatic Code

def minDistance(word1: str, word2: str) -> int:
    if len(word1) < len(word2):
        word1, word2 = word2, word1
    dp = list(range(len(word2) + 1))
    for i, c1 in enumerate(word1, 1):
        diag = dp[0]
        dp[0] = i
        for j, c2 in enumerate(word2, 1):
            up = dp[j]
            dp[j] = diag if c1 == c2 else 1 + min(up, dp[j - 1], diag)
            diag = up
    return dp[-1]

4. Failure Modes & Interview Follow-ups

Pitfalls:- Neglecting to re-seed `dp[0] = i` before each row loses cost of deleting prefix `w1[:i]` to empty string `""`. - Overwriting `dp[j]` without caching `diag` into `prev` corrupts replacement transitions.

Follow-ups:- Myers diff / patience diff optimizes when differences are small (O((M+N)*D)) — used inside git diff and `fast-diff`.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Longest Common Subsequence (O(M * N))Interleaving String (O(M * N))

Browser Scratchpad

Console Output

Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.