Visual walkthrough — DP problems — edit distance (Levenshtein)

3.7.12 · D2 · Coding › Algorithm Paradigms › DP problems — edit distance (Levenshtein)

Yahan sab kuch Dynamic Programming ka slow-motion replay hai jo strings par apply kiya gaya hai.

---

Step 1 — "String" kya hoti hai aur "edit" kya hota hai?

KYA. Ek string bas letters ki ek row hai jo left se right likhi jaati hai, jaise wire par beads: A = h o r s e. Hum beads ko position 0 se number karte hain, toh A[0]='h', A[1]='o', wagera. Beads ki sankhya length hai, jise $m$ likha jaata hai.

KYUN. Jab tak hum agree nahi karte ki ek edit kya hai, tab tak hum "edits" count nahi kar sakte. Exactly teen moves hain, aur har ek ki cost 1 coin hai:

• insert — wire par ek naya letter chipka do.
• delete — wire se ek letter kheench lo.
• substitute — ek letter ko doosre se badal do.

PICTURE. Teeno moves ek hi chhote word par dikhaye gaye hain, neeche coin cost print ki gayi hai. Yeh problem ki poori "vocabulary" hai — aur kuch allowed nahi hai.

---

Step 2 — Problem ko prefixes mein kyun kaatein

KYA. Ek prefix hota hai "word ke pehle kuch letters". A[0..i) ka matlab hai "$A$ ke pehle $i$ letters" — yeh chhota half-open bracket [0..i) padha jaata hai position 0 se lekar position $i$ tak lekin $i$ include nahi. Toh A[0..0) empty word hai (zero letters), aur A[0..5) poora horse hai.

KYUN. horse → ros ek saath solve karna daraawaana lagta hai. Lekin h → r (ek-ek letter) solve karna bilkul chhota hai. Dynamic Programming ki poori trick yahi hai: pehle har chhota prefix pair solve karo, answer likho, aur reuse karo. Chhote answers ka yeh reuse exactly Optimal Substructure aur Overlapping Subproblems hai.

PICTURE. Do words jismein ek "cut line" dono par slide karti hai, growing length ke prefixes dikhate hue. $A$ par har cut ek index $i$ hai; $B$ par har cut ek index $j$ hai.

---

Step 3 — Base row aur base column (free walls)

KYA. Do special situations jahan answer ke liye sochna nahi padta:

• Ek word empty hai. Empty word "" ko B[0..j) mein badalna — uski cost kya hai? Tumhare paas kuch nahi hai aur $j$ letters chahiye, toh tum $j$ baar insert karte ho: $dp[0][j]=j$.
• Doosra word empty hai. A[0..i) ko "" mein badalna matlab uske saare $i$ letters delete karna: $dp[i][0]=i$.

KYUN. Har recurrence eventually apne inputs ko chhhota karta hai; kuch toh shrinking ko rokna chahiye. Yeh do "walls" woh floor hain. Inke bina grid mein koi starting numbers nahi hain jis par build kiya ja sake (parent ki "forgetting the base row/column" mistake dekho).

PICTURE. Empty grid jismein top row 0 1 2 3... se bhari hai (saari inserts) aur left column 0 1 2 3... se bhari hai (saare deletes). Corner $dp[0][0]=0$ (empty → empty, zero coins).

---

Step 4 — Har cell ka ek sawaal: "last letters ka kya?"

KYA. Koi bhi inner cell $dp[i][j]$ lo. Current letters dekho — kyunki hum pehle $i$ se count karte hain, us prefix ka last letter index $i-1$ par hai. Toh do letters jo play mein hain woh hain A[i-1] aur B[j-1] (yeh off-by-one parent ki #1 mistake hai — cell letters count karta hai, isliye naaya letter index minus one par hai).

KYUN. Edits ka koi bhi poora sequence dono prefix ke last letter se deal karke khatam hona chahiye. Sirf kuch hi possible "last moves" hain, aur — important baat — jab ek baar hum last move decide kar lete hain, toh us se pehle sab kuch ek chhota cell hai jo hum pehle hi bhar chuke hain. Isliye ek sawaal kaafi hai.

PICTURE. Do prefix strips jismein unke final letters highlighted hain, aur ek thought-bubble jismein sirf possible last moves listed hain.

---

Step 5 — Case A: last letters MATCH hain (free diagonal)

KYA. Agar A[i-1] == B[j-1], toh final letters already agree karte hain. Hum yahan zero coins kharach karte hain aur sirf do chhote prefixes align karne ki cost inherit karte hain (dono se last letter drop karo):

$dp[i][j]=dp[i-1][j-1]\text{(no }+1\text{)}$

KYUN. Diagonal $dp[i-1][j-1]$ kyun aur up ya left kyun nahi? Kyunki dono words se ek-ek letter drop karna grid mein diagonally up-and-left le jaata hai. $+1$ kyun nahi? Kyunki matching letters ko koi edit nahi chahiye — yahan ek coin add karna over-count hoga (parent ki "min over the wrong neighbours" mistake).

PICTURE. Grid arrow jo up-left neighbour se current green cell mein point kar raha hai, o == o labelled hai aur "0 coins" tag lagaa hai.

---

Step 6 — Case B: last letters DIFFER karte hain (teen rescue routes)

KYA. Agar A[i-1] != B[j-1], toh hume ek coin kharach karni padegi, lekin hamare paas kharach karne ke teen tarike hain. Har route $1$ pay karta hai aur phir ek already-solved neighbour par lean karta hai:

$dp[i][j]=1+\min (\underset{\text{substitute}}{\underbrace{dp[i-1][j-1]}},\underset{\text{delete from }A}{\underbrace{dp[i-1][j]}},\underset{\text{insert into }A}{\underbrace{dp[i][j-1]}})$

• ↖ Substitute — A[i-1] ko B[j-1] se swap karo; dono prefixes ek-ek shrink hote hain → diagonal neighbour, $+1$.
• ↑ Delete — extra letter A[i-1] fenko; sirf $A$ shrink hota hai → cell upar, $+1$.
• ← Insert — zaroori letter B[j-1] add karo; sirf $B$ shrink hota hai → cell baayein, $+1$.

KYUN. Hum minimum lete hain kyunki hum sabse sasta fix chahte hain, aur yeh teeno sirf possible last moves hain — toh hum best ko kabhi miss nahi kar sakte.

PICTURE. Current red cell mein teen incoming arrows (↖ substitute, ↑ delete, ← insert), har ek apne neighbour aur apne +1 ke saath labelled, aur min sabse chhota pick kar raha hai.

---

Step 7 — Ek real cell fill hote dekho: dp[5][3] for horse → ros

KYA. Hum poora grid bharte hain, phir bottom-right cell par zoom in karte hain. Yahan A[4]='e', B[2]='s', aur 'e' ≠ 's', isliye hum differ rule use karte hain:

$dp[5][3]=1+\min (\underset{3}{\underbrace{dp[4][2]}},\underset{2}{\underbrace{dp[4][3]}},\underset{4}{\underbrace{dp[5][2]}})=1+2=3$

KYUN. Teen candidates hain $3,2,4$; sabse chhota $2$ hai (cell upar, matlab "e delete karo"). Ek coin add karo aur hum 3 par pahunchte hain — final answer $d(\text{horse},\text{ros})=3$.

PICTURE. Completed $6\times 4$ grid, diagonal match cells shaded hain, aur ek coloured back-trace path jo delete h, delete r, substitute e→s dikhata hai.

---

Step 8 — Degenerate cases (koi unseen scenario kabhi mat hit karo)

KYA. Problem ke corners:

• Dono empty: $d(\text{""},\text{""})=dp[0][0]=0$.
• Ek empty: $d(\text{""},\text{"abc"})=3$ (pure base row) aur $d(\text{"abc"},\text{""})=3$ (pure base column).
• Identical words: har letter match karta hai, poora path free diagonal hai → $d(A,A)=0$.
• Same length, sab alag: jaise abc → xyz — koi match nahi, teen substitutions → distance $3$. Yeh dikhata hai ki length difference (yahan $0$) sirf ek lower bound hai, answer kabhi nahi (parent ki last mistake).

KYUN. Yeh woh boundaries hain jahan recurrence "bottom out" karta hai. Agar inme se koi bhi galat hota, toh upar bane har cell mein galti aati.

PICTURE. Chaar mini-grids side by side, har ek ek degenerate case ke liye, har ek ka answer circled hai.

---

Ek-picture summary

KYA. Ek figure jismein poori derivation hai: base walls (Step 3), match diagonal (Step 5), three-arrow choice (Step 6), aur corner mein answer (Step 7).

Recall Poori walkthrough ki Feynman retelling

Dono words ko ek wire par rakho. Ek grid banao: rows count karti hain ki tum pehle word ke kitne letters dekh rahe ho, columns count karti hain ki doosre ke kitne. Top row aur left column free warm-ups hain — kuch nahi se ek word banana bas har letter insert karna hai, aur ek word ko kuch nahi mein badhana bas har letter delete karna hai, toh unhe 0 1 2 3... se bharo. Ab har doosra box ek tiny sawaal poochta hai: kya do naaye letters match karte hain? Agar haan, toh diagonally up-left waale box ko copy karo — matching free hai. Agar nahi, toh ek coin kharach karni padegi, aur tum teen neighbours mein se sabse sasta choose kar sakte ho: up-left (ek letter swap karo), seedha upar (pehle word se ek letter delete karo), ya seedha baayein (ek letter add karo). Boxes left-to-right, top-to-bottom bharo, aur jis pal tum bottom-right corner mein sabse last box bharte ho, wahan sabse-kam-coins answer likha hoga.

---

Connections

• Parent: Edit Distance — yeh page uski visual derivation hai.
• Dynamic Programming · Optimal Substructure · Overlapping Subproblems — grid kyun kaam karta hai.
• Recursion and Memoization — wahi recurrence, top-down.
• Longest Common Subsequence · Sequence Alignment — match-diagonal in dono ke saath shared hai.
• Space Optimization in DP — grid ki sirf ek row rakho.