Worked examples — DP problems — edit distance (Levenshtein)

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

Is page mein hum har tarah ki input dhundte hain jo edit distance throw kar sakti hai, aur har ek ko ground up se work karte hain. Agar parent note ne tumhe machine sikhaayi thi, toh yeh page stress test hai — hum isme empty strings, identical strings, single characters, aisi strings jahan har letter galat hai, ek real-world spell-checker, aur ek exam twist daaalte hain, taaki tum kabhi aisa case na dekho jo tumne pehle dekha na ho.

Pehle, teen symbols earn karne padte hain, usse pehle kuch bhi unhe use kare: do strings $A$ aur $B$, aur distance function $d$.

Ab woh rule jo sab kuch drive karta hai (poori tarah parent note mein build kiya gaya hai):

Yahan "pehle $i$ letters" ka matlab hai: string ko position $i$ ke baad kaato. $A=$cat ke liye, "pehle 2 letters" hain ca. Woh letter jis ke baare mein hum abhi decide kar rahe hain woh hai $A[i-1]$ — us chop mein aakhri wala. Yeh $-1$ sabse common bug hai, isliye hum har example mein current letters zor se bolenge.

---

Scenario matrix

Har edit-distance problem in case classes mein se ek mein aata hai. Neeche hamara kaam hai ki har row ko ek fully worked example se bharein. (Yaad karo $m=|A|$, $n=|B|$ upar ki definitions se.)

#	Case class	Kya khaas hai	Covered by
C1	Dono empty	Degenerate: kuch karna nahi	Example 1
C2	Ek empty, ek non-empty	Pure base case (sab inserts ya sab deletes)	Example 1
C3	Identical strings	Har char match karta hai — diagonal 0 carry karta hai	Example 2
C4	Single-char, equal vs unequal	Sabse chhota non-empty case, dono branches	Example 3
C5	Equal length, kuch substitutions	Sirf swaps se distance, koi length change nahi	Example 4
C6	Different length, mixed ops	Insert/delete aur substitute saath mein	Example 5
C7	Completely disjoint alphabets	Worst case — distance $=\max (m,n)$	Example 6
C8	Prefix/suffix contained	Ek string doosre ke andar hai	Example 7
C9	Real-world word problem	Spell-checker suggestion cost	Example 8
C10	Exam twist: multiple optimal paths	Same distance, alag edit scripts	Example 9

Hum poore samay ek sanity bound bhi use karte hain: distance hamesha $|m-n|$ (length gap — ek lower bound, kyunki tum gap close karne se bach nahi sakte) aur $\max (m,n)$ (longer string ki length — ek upper bound, kyunki worst case mein tum ek letter per op fix karte ho) ke beech hoti hai. Symbols mein:

$|m-n|\le d(A,B)\le \max (m,n)$

Hum is band ko har example mein dobara check karenge — yeh kisi arithmetic slip ko pakadne ka sabse fast tarika hai.

Neeche wali figure is band ko ek number line par plot karti hai, jisme real distance (red dot) sunday→saturday example ke liye iske andar fansa hua hai jo hum Example 5 mein solve karte hain.

Figure s01 — $0$ se $8$ tak ka ek horizontal number line. Ek black double-headed arrow allowed band ko lower bound $|m-n|=2$ se upper bound $\max (m,n)=8$ tak span karta hai. Red dot actual answer $d=3$ mark karta hai, band ke andar baitha hai. Ise padhna: koi bhi legal distance $2$ se left ya $8$ se right nahi ja sakti. Hum Example 5 mein exactly isi picture par wapas aayenge.

---

Example 1 — Empty strings (C1 + C2)

Forecast: Aage padhne se pehle teeno guess karo. Empty→empty lagta hai… kuch nahi. Empty→3-letter lagta hai… 3 builds. 3-letter→empty lagta hai… 3 removals.

Steps.

1. $d(\text{""},\text{""})=dp[0][0]=0$ ($d(A,B)=dp[|A|][|B|]$ use karte hue, dono lengths $0$ ke saath). Yeh step kyun? Do empty strings pehle se identical hain; zero moves. Yeh woh seed hai jisse har table grow karti hai.
2. $d(\text{""},\text{"cat"})=dp[0][3]$. Base-case rule kehta hai $dp[0][j]=j$, toh $dp[0][3]=3$. Yeh step kyun? Kuch nahi se tum sirf insert kar sakte ho. c, phir a, phir t produce karne ke liye tum teen baar insert karte ho — koi sasta move nahi hai kyunki deletes aur substitutions ko act karne ke liye ek existing letter chahiye.
3. $d(\text{"dog"},\text{""})=dp[3][0]$. Base-case rule kehta hai $dp[i][0]=i$, toh $dp[3][0]=3$. Yeh step kyun? Empty string tak pahunchne ke liye tum sirf delete kar sakte ho — d, o, g hatao, teen deletes.

Verify: Middle case ke liye, $m=|\text{""}|=0$, $n=|\text{"cat"}|=3$. Lower bound $|m-n|=|0-3|=3$; upper bound $\max (0,3)=3$. Answer $3$ bilkul dono ke beech pinched hai, toh sahi hona chahiye. ✅ (dog→"" case mirror image hai, $|3-0|=3=\max$.)

---

Example 2 — Identical strings (C3)

Forecast: Same word, dono taraf. Aage padhne se pehle number guess karo.

Steps.

1. $A=B=$apple, toh $m=|A|=5$ aur $n=|B|=5$ — equal lengths. Diagonal bharo. $dp[1][1]$ par: current letters $A[0]=$a, $B[0]=$a — woh match karte hain, toh $dp[1][1]=dp[0][0]=0$. Yeh step kyun? Match diagonal ko bina +1 ke copy karta hai (match branch). Zero cost carry hota rehta hai.
2. Har subsequent diagonal cell match karta hai (p=p, p=p, l=l, e=e), toh $dp[2][2]=dp[3][3]=dp[4][4]=dp[5][5]=0$. Yeh step kyun? Har current-letter pair equal hai, toh har step $0$ ko diagonal se re-copy karta hai. Neeche figure mein $0$s ki seedhi red diagonal dekho.
3. Final answer $d(A,B)=dp[5][5]=0$.

Figure s02 — apple→apple ke liye poora $6\times 6$ DP table. Columns B=apple se headed hain, rows A=apple se. Base row aur column $0,1,2,3,4,5$ tak black mein count karte hain. Red diagonal $0$s ki top-left se bottom-right tak run karti hai; red arrow answer $dp[5][5]=0$ par point karta hai. Har matched letter cell ko up-and-left se copy karta hai, toh zeros seedhe neeche ride karte hain.

Verify: Distance $0$ ka matlab hai "pehle se equal" — aur strings hain hi identical, toh koi edit possible ya zaruri nahi. Sanity band: $|m-n|=|5-5|=0\le 0\le \max (5,5)=5$. Answer lower bound par baitha hai, exactly wahan jahan identical strings honi chahiye. ✅

---

Example 3 — Single characters, dono branches (C4)

Forecast: Ek match hai, ek mismatch. Ek ka cost $0$ hona chahiye, doosre ka $1$ — kaun sa kaun sa hai?

"a"→"a" ke liye Steps.

1. Table $2\times 2$ ki hai. Bases: $dp[0][0]=0$, $dp[0][1]=1$, $dp[1][0]=1$. Yeh step kyun? Row 0 aur column 0 $dp[1][1]$ touch karne se pehle exist karne chahiye — yeh wahi "base bhool gaye" mistake hai parent note se.
2. $dp[1][1]$: current letters $A[0]=$a, $B[0]=$a match karte hain → $dp[1][1]=dp[0][0]=0$. Toh $d(\text{"a"},\text{"a"})=0$. Yeh step kyun? Match branch, pure diagonal, koi +1 nahi.

"a"→"b" ke liye Steps.

3. $dp[1][1]$: $A[0]=$a, $B[0]=$b alag hain → $1+\min (dp[0][0],dp[0][1],dp[1][0])=1+\min (0,1,1)=1$. Toh $d(\text{"a"},\text{"b"})=1$. Yeh step kyun? Sabse sasta predecessor diagonal $dp[0][0]=0$ hai, matlab hum ek coin mein a→b substitute karte hain (Levenshtein ka substitute operation — transposition nahi; Levenshtein mein "do letters swap karo" ka koi move nahi hai). a delete karke b insert karna $2$ cost karta — min sahi se use reject karta hai.

Verify: "a"→"a" $0$ deta hai; sanity band $|1-1|=0\le 0\le \max (1,1)=1$. ✅ "a"→"b" $1$ deta hai; band $0\le 1\le 1$, aur $m=n=1$ hone se poora cost ek substitution hai, kabhi koi length change nahi. ✅

---

Example 4 — Equal length, sirf substitutions (C5)

Forecast: Har pair mein dono strings ki equal length hai. Guess karo: kya equal length answer ko pure substitutions hone par force karti hai?

"cat"→"cot" ke liye Steps. Yahan $m=n=3$.

1. $dp[1][1]$: c=c match → $dp[1][1]=dp[0][0]=0$. Yeh step kyun? Match branch $0$ aage carry karta hai.
2. $dp[2][2]$: current letters $A[1]=$a, $B[1]=$o alag hain → $1+\min (dp[1][1],dp[1][2],dp[2][1])=1+\min (0,1,1)=1$. Yeh step kyun? Min diagonal predecessor $dp[1][1]=0$ pick karta hai, yaani a→o substitute karo. Delete path ($dp[1][2]$) aur insert path ($dp[2][1]$) dono $1$ cost karte hain, toh $1+1=2$ each — recurrence inhe reject karta hai kyunki substitution yahan strictly sasti hai. Yeh wahi "substitute kyun, delete+insert kyun nahi" hai jo formula automatically settle kar deta hai.
3. $dp[3][3]$: t=t match → $dp[3][3]=dp[2][2]=1$. Toh $d(\text{"cat"},\text{"cot"})=1$.

"abcd"→"wxyz" ke liye Steps. Yahan $m=n=4$.

4. Har diagonal cell mein alag letters hain (a≠w, b≠x, c≠y, d≠z). Har ek par, diagonal predecessor delete/insert neighbours ko exactly usi $1$-vs-$2$ margin se beat karta hai jaise Step 2 mein, toh har ek ek substitution contribute karta hai: $dp[1][1]=1$, $dp[2][2]=2$, $dp[3][3]=3$, $dp[4][4]=4$. Yeh step kyun? Jab lengths equal hain, toh har diagonal cell par min-over-three hamesha substitution (cost $1$) ko delete+insert pair (cost $2$) ke upar prefer karta hai. Isliye total $4$ substitutions.

Verify: "cat"→"cot" $1$ deta hai; sanity band $|3-3|=0\le 1\le \max (3,3)=3$. ✅ "abcd"→"wxyz" $4$ deta hai; band $0\le 4\le 4$ — yeh upper bound par baitha hai kyunki har letter ko kaam ki zarurat thi. ✅

---

Example 5 — Different length, mixed operations (C6)

Forecast: In dono mein s…day share hai. Guess karo: $8$ target letters mein se kitne ko real kaam ki zarurat hai.

Steps.

1. DP table row by row bharo (rows = sunday, columns = saturday). Neeche ki table recurrence se compute ki gayi hai; bottom-right answer se top-left corner tak red back-pointer path trace karo.

Figure s03 — sunday→saturday ke liye $7\times 9$ DP table. Rows A=sunday se headed hain, columns B=saturday se. Bottom-right cell mein answer $3$ hai. Red staircase $dp[6][8]$ se $dp[0][0]$ tak ek optimal back-pointer path trace karta hai: matched letters par diagonal moves (free) aur teen costly moves — do inserts aur ek substitute.

2. Shared letters s…u…d-a-y diagonal par free line up karte hain — yeh red path ke woh diagonal steps hain jahan letters match karte hain. Kya bacha: saturday mein extra a aur t hain jo sunday mein nahi hain → 2 insert karo (path mein do leftward steps). Aur sunday ka n r banana padega → 1 substitute karo (ek diagonal step jahan letters alag hain). Yeh step kyun? Matches free hain, toh free diagonal run positions ka ek set trace karta hai jo dono strings mein order mein agree karte hain. Yahi woh jagah hai jahan LCS connection precise hai: free (match) diagonal steps ek common subsequence form karte hain — lekin plain Levenshtein use maximise nahi karta. Do related lekin alag DPs: LCS matches count karta hai maximise karne ke liye; Levenshtein edits count karta hai minimise karne ke liye, aur sirf tab jab substitution aur insert/delete sab $1$ cost karte hain, toh identity $d(A,B)=m+n-2\cdot \text{LCS}(A,B)$ satisfy hoti hai sirf substitution-free (LCS) edit model ke liye. Hum yahan us identity par rely nahi karte; bas observe karte hain ki longer shared runs distance ko shrink karti hain.
3. Total $=2+1=3$.

Verify: Figure s01 par wapas, jiska band is example ke liye build kiya gaya tha: lower bound $|m-n|=|6-8|=2$; hamara answer $3>2$ (extra $1$ forced substitution hai), aur $3\le \max (6,8)=8$. s01 mein red dot exactly $3$ par baitha hai, band ke andar. ✅

---

Example 6 — Disjoint alphabets, worst case (C7)

Forecast: Koi common letters nahi, aur lengths $3$ vs $4$. Guess karo ki kya answer $\max (3,4)$ hai.

Steps.

1. Kuch bhi match nahi karta, isliye har cell "differ" branch mein jaata hai — koi free diagonals exist nahi karti. Neeche ki table poora grid dikhati hai; answer bottom-right cell hai.

Figure s04 — abc→xyzw ke liye $4\times 5$ DP table jisme letters poori tarah disjoint hain. Rows A=abc se headed hain, columns B=xyzw se. Kyunki koi letters match nahi karte, values sirf badhti hain; red bottom-right cell answer $4$ dikhata hai, $\max (m,n)$ ke equal. Red path teen substitutions aur ek insert ka mix hai.

2. Path padhte hue: a→x, b→y, c→z substitute karo (teen substitutions), phir w insert karo — total $3+1=4$. Yeh step kyun? Jab alphabets disjoint hain, koi free matches exist nahi karte, toh distance apni ceiling tak pahunch jaati hai: longer string ki length. Tum longer string ke har letter par ek op spend karte ho.

Verify: Sanity band $|m-n|=|3-4|=1\le 4\le \max (3,4)=4$. ✅ Disjoint case exactly upper bound saturate karta hai — in lengths ki koi bhi input $4$ se zyada cost nahi kar sakti.

---

Example 7 — Ek string doosre ki substring hai (C8)

Forecast: Pehle mein, kya cat cart ke andar chhupa hai? Doosre mein, kya cat scatter ka ek chunk hai? Sirf "extra letters" se har distance guess karo.

"cart"→"cat" ke liye Steps. Yahan $m=4$, $n=3$.

1. Neeche ki DP table (top panel) alignment dikhati hai. Red path follow karo: c matches c, a matches a (diagonal, free), phir cart mein abhi bhi apne t se pehle r hai jabki cat seedha t par jaata hai — r leftover hai → use delete karo (ek upward step).

Figure s05 — do stacked DP tables, har ek apne axes labeled ke saath. Top: cart→cat ke liye $5\times 4$ table; left axis A=cart (rows) labeled hai, top axis B=cat (cols), aur base row/column ($0,1,2,3$) annotated hain. Red path do free diagonal matches phir ek upward delete step dikhata hai, answer $1$. Bottom: cat→scatter ke liye $4\times 8$ table; left axis A=cat (rows), top axis B=scatter (cols), base row/column annotated. Red path cat ke through ek free diagonal run dikhata hai jo s aur ter ke liye leftward insert steps se bracket hua hai, answer $4$.

2. Toh ek extra letter r → distance $1$.

"cat"→"scatter" ke liye Steps. Yahan $m=3$, $n=7$.

3. scatter = s + cat + ter. Hume front mein s aur back mein t,e,r insert karne padte hain → $1+3=4$ inserts. cat ka poora middle mein free match hota hai (bottom table mein free diagonal run). Yeh step kyun? Jab ek string doosre ke letters ko order mein plus extras ke saath contain karti hai, toh har extra ek single delete/insert hai.

Verify: "cart"→"cat": sanity band $|m-n|=|4-3|=1\le 1\le \max (4,3)=4$ — answer lower bound par baitha hai kyunki sirf deletions ki zarurat thi. ✅ "cat"→"scatter": band $|3-7|=4\le 4\le \max (3,7)=7$ — phir lower bound par, pure insertions, koi substitution nahi kyunki cat cleanly embed hota hai. ✅

---

Example 8 — Real-world word problem: spell-checker (C9)

Forecast: Dono candidates $7$ letters ke hain, typo ki tarah same. Guess karo kaun sa correction "closer" hai.

Steps.

1. Dono candidate distances DP table bharne se aati hain; figure do answer cells side by side dikhati hai taaki tum dekh sako kaun sa chhota hai.

Figure s06 — do DP tables, ek har candidate ke liye. Left: recieve→receive, uska bottom-right answer cell red mein $2$ padhta hai. Right: recieve→relieve, uska red answer cell $1$ padhta hai. Chhota red number ranking jeet ta hai.

2. "recieve" → "receive": equal lengths ($m=n=7$), toh letter-for-letter align karo. r-e-c match karte hain, phir typo mein i-e hai jahan correct word mein e-i hai — reversed, toh do substitutions (i→e aur e→i), phir v-e match. Distance $2$. Yeh step kyun? Equal lengths → position-by-position align karo; do positions differ karte hain → do substitutions.
3. "recieve" → "relieve": r-e match karte hain, phir c vs l differ karte hain (+1 substitute), i-e-v-e sab match karte hain. Sirf ek position differ karti hai → distance $1$.
4. Compare karo: receive $2$ cost karta hai, relieve $1$ cost karta hai. Checker "relieve" pehle rank karta hai raw edit distance se. Yeh step kyun matter karta hai? Real spell-checkers precisely isliye dictionary-frequency tie-breaker add karte hain kyunki raw distance "galat" word ko favour kar sakta hai — lekin pure Levenshtein par, relieve jeet ta hai.

Verify: Teeno words ki length $7$ hai. receive: band $|7-7|=0\le 2\le 7$; relieve: band $0\le 1\le 7$. Dono distances pure-substitution counts hain ($2$ aur $1$) kyunki $m=n$. ✅

---

Example 9 — Exam twist: do optimal paths, same distance (C10)

Forecast: Letters same hain, bas reorder hue hain. Levenshtein mein koi transposition operation nahi hai (tum ek move mein do letters swap nahi kar sakte), toh reorder free nahi hai — cost guess karo.

Steps.

1. $3\times 3$ table banao ($m=n=2$). Bases: $dp[0][\cdot ]=0,1,2$ aur $dp[\cdot ][0]=0,1,2$. Phir $dp[1][1]=1$ (a≠b, substitute), $dp[1][2]=1$ (a=a match, $dp[0][1]=1$ carry karta hai), $dp[2][1]=1$ (b=b match, $dp[1][0]=1$ carry karta hai), aur $dp[2][2]=1+\min (dp[1][1],dp[1][2],dp[2][1])=1+\min (1,1,1)=2$.

Figure s07 — ab→ba ke liye $3\times 3$ DP table, answer $2$ red bottom-right cell mein. Teen red arrows us cell se saare teen predecessors ($dp[1][1]$, $dp[1][2]$, $dp[2][1]$) par fan out karte hain, jo sab $1$ par tie karte hain. Kyunki teen back-pointers equally optimal hain, ek se zyada edit script minimum achieve karti hai.

2. $dp[2][2]$ par saare teen predecessors $1$ par tie karte hain, toh figure teen red back-pointer arrows draw karti hai — yahi tie exactly woh reason hai kyun multiple optimal edit scripts exist karti hain. Do natural scripts:
   • a→b substitute karo, phir b→a substitute karo.
   • a delete karo, phir end mein a insert karo (ek "rotate" delete+insert ke roop mein). Dono $2$ cost karte hain. Yeh step kyun? Bottom-right se top-left tak har distinct back-pointer path ek distinct edit script mein decode hoti hai jisme same total cost hai.

Verify: Levenshtein mein koi transposition operation nahi hai, isliye do adjacent letters swap karne ki cost $2$ hai, $1$ nahi. Sanity band $|m-n|=|2-2|=0\le 2\le \max (2,2)=2$ — upper bound par baitha hai. ✅ (Agar transpositions allowed hote — Damerau–Levenshtein variant — toh answer $1$ hota; standard Levenshtein $2$ deta hai.)

---

Recall Matrix ke across quick self-test

Answers cover karo aur har ek reconstruct karo. $d(\text{""},\text{""})$ ::: $0$ $d(\text{""},\text{"cat"})$ ::: $3$ (teen inserts) $d(\text{"apple"},\text{"apple"})$ ::: $0$ (identical) $d(\text{"a"},\text{"b"})$ ::: $1$ (ek substitution) $d(\text{"cat"},\text{"cot"})$ ::: $1$ (ek substitution) $d(\text{"abcd"},\text{"wxyz"})$ ::: $4$ (char substitutions) $d(\text{"sunday"},\text{"saturday"})$ ::: $3$ $d(\text{"abc"},\text{"xyzw"})$ ::: $4$ (worst case $=\max$) $d(\text{"cart"},\text{"cat"})$ ::: $1$ (r delete karo) $d(\text{"cat"},\text{"scatter"})$ ::: $4$ (char inserts) $d(\text{"recieve"},\text{"relieve"})$ ::: $1$ $d(\text{"ab"},\text{"ba"})$ ::: $2$ (free transposition nahi)

---

Connections

• Parent: Edit Distance — woh machine jinhe yeh examples stress-test karti hain.
• Longest Common Subsequence — free diagonal run ek shared subsequence se relate karta hai (Example 5), though LCS maximise karta hai matches ko jabki Levenshtein minimise karta hai edits ko.
• Sequence Alignment — spell-checking (Example 8) small-scale alignment hai.
• Optimal Substructure · Overlapping Subproblems — kyun recurrence upar har case par sahi hai.
• Recursion and Memoization — inhe compute karne ka top-down tarika.
• Space Optimization in DP — upar ki har table ko sirf previous row chahiye.
• Dynamic Programming — umbrella paradigm.