DP problems — edit distance (Levenshtein) — Hinglish notes

3.7.12 · Coding › Algorithm Paradigms

WHAT is it?

Hum ek 2D table define karte hain:

$d p [i] [j] = edit distance between the first i chars of A and the first j chars of B$

Toh $d p [m] [n]$ humara final answer hai, aur $d p [0] [0] = 0$ (do empty strings ki cost kuch nahi).

WHY does a recurrence even exist?

Aakhri move in mein se ek hoga:

Characters match karte hain (A[i-1] == B[j-1]): is position ke liye koi edit nahi chahiye → cost $d p [i - 1] [j - 1]$ se pass through hoti hai.
Substitute A[i-1] → B[j-1]: cost $1 +$ chhote prefixes $d p [i - 1] [j - 1]$ ko align karne ki cost.
Delete A[i-1] (yeh A mein extra char hai): cost $1 + d p [i - 1] [j]$ .
Insert B[j-1] (yeh B mein chahiye): cost $1 + d p [i] [j - 1]$ .

Hum minimum lete hain kyunki hum sabse sasta raasta chahte hain.

HOW to derive the recurrence from scratch

Yeh kyun sahi hai: har conversion exactly upar diye chaar cases mein se ek ke saath khatam hoti hai, har ek strictly chhote subproblem par reduce hoti hai, aur hum minimize karte hain — toh hum kabhi optimum miss nahi karte (yeh optimal substructure + overlapping subproblems hai).

Figure — DP problems — edit distance (Levenshtein)

Complexity (80/20 takeaway)

Time: $O (m \cdot n)$ — hum har cell ko ek baar $O (1)$ mein fill karte hain.
Space: $O (m \cdot n)$ full table ke liye, ya $O (min (m, n))$ agar aap sirf previous row rakhte ho (aap sirf row $i - 1$ aur column $j - 1$ hi padhte ho).

Worked Example 1 — `"horse"` → `"ros"` (answer = 3)

Hum table ko row by row fill karte hain. Maano $A =$ horse (rows), $B =$ ros (cols).

		""	r	o	s
		0	1	2	3
h	1	1	1	2	3
o	2	2	2	1	2
r	3	3	2	2	2
s	4	4	3	3	2
e	5	5	4	4	3

Kyun $d p [2] [2] = 1$ ? A[1]='o', B[1]='o' match karte hain, toh hum diagonal $d p [1] [1] = 1$ copy karte hain. Yeh step kyun? Match karne ki cost kuch nahi, toh cost chhote prefixes "h"→"r" fix karne ke barabar hai.
Kyun $d p [5] [3] = 3$ ? 'e' ≠ 's', toh $1 + min (d p [4] [2], d p [4] [3], d p [5] [2]) = 1 + min (3, 2, 4) = 3$ . Yeh step kyun? Sabse sasta predecessor delete path hai (e delete karo), jo final 3 deta hai.
Edits wapas padhna: h→r substitute karo? Nahi — actual optimal path hai delete h, delete r, substitute e→s (3 edits), jo $d p [5] [3] = 3$ se match karta hai.

Worked Example 2 — `"sunday"` → `"saturday"` (answer = 3)

Key cells:

Shared s...n...day structure ka matlab hai ki bahut saare matches seedha diagonal ke neeche jaate hain.
Hume a aur t insert karne padte hain, aur n→r substitute karna padta hai. Yeh $2 + 1 = 3$ hai.

Yeh 3 kyun hai aur zyada kyun nahi? Kyunki lambi common subsequence s..day free mein align ho jaati hai; sirf 3 positions par actually kaam karna padta hai. Yeh step kyun important hai: edit distance secretly lambi shared subsequences ko reward karta hai.

Worked Example 3 — Forecast-then-Verify

Common Mistakes

Recall Feynman: 12-saal ke bachche ko explain karo

Socho tumhare paas do words Lego strips par likhe hain aur tum pehli word ko bilkul doosri jaisi dikhana chahte ho. Tumhe teen moves ki permission hai: ek nayi letter brick chipkaao, ek letter brick khicho, ya ek brick ko doosre se badlo — har move mein ek coin lagti hai. Edit distance woh sabse kam coins hai jo tum kharch kar sakte ho. Clever trick: poori word ek saath solve karne ki jagah, tum ek chhota grid banate ho aur pehle chhoti shuruat ke liye sabse sasta fix pata karte ho (sirf ek letter, phir do...), har answer ek box mein likhte ho. Har naya box sirf teen boxes pe nazar daalta hai jo tumne pehle fill kiye hain (upar, baayi taraf, aur upar-baayi taraf diagonal) aur sabse sasta choose karta hai. Jab tak tum bottom-right box tak pahuncho, answer wahan already ready milta hai!

Active Recall

Edit distance mein

d p [i] [j]

kya represent karta hai?

A

ke pehle

i

chars aur

B

ke pehle

j

chars ke beech minimum edit distance.

Teen allowed operations aur unki costs kya hain?

Insert, delete, substitute — har ek ki cost 1 hai.

d p [0] [j]

kya hai aur kyun?

j

— empty string se B[0..j) banane ke liye aapko

j

characters insert karne padte hain.

d p [i] [0]

kya hai aur kyun?

i

— A[0..i) ko empty karne ke liye aapko

i

characters delete karne padte hain.

Jab A[i-1] == B[j-1] ho, toh

d p [i] [j]

kya hai?

d p [i - 1] [j - 1]

(diagonal, bina kisi +1 ke).

Jab characters alag hon, transition likhो.

1 + min (d p [i - 1] [j - 1], d p [i - 1] [j], d p [i] [j - 1])

A se deletion kaunsa neighbour represent karta hai?

Seedha upar wala cell,

d p [i - 1] [j]

A mein insertion kaunsa neighbour represent karta hai?

Baayi taraf wala cell,

d p [i] [j - 1]

Time aur space complexity?

O (mn)

time;

O (mn)

space, ek row rakh ke

O (min (m, n))

tak reduce ho sakta hai.

Recurrence sirf aakhri character kyun dekhta hai?

Koi bhi edit sequence har prefix ke final char ko handle karti hai; use fix karna ek chhote solved subproblem par reduce hota hai (optimal substructure).

"horse" → "ros" ki edit distance?

Kya edit distance length difference ke barabar hoti hai?

Nahi — yeh sirf ek lower bound hai; substitutions equal length par bhi cost add karti hain.

Connections

Dynamic Programming — edit distance ek canonical 2D-table DP hai.
Longest Common Subsequence — closely related; LCS matches align karta hai, edit distance mismatches count karta hai.
Optimal Substructure — woh property jo recurrence ko valid banati hai.
Overlapping Subproblems — isliye memoisation/tabulation naive recursion se better hai.
Recursion and Memoization — bottom-up table ka top-down alternative.
Sequence Alignment — bioinformatics generalisation (Needleman–Wunsch) weighted costs ke saath.
Space Optimization in DP — rolling-row trick jo $O (min (m, n))$ space tak pahunchata hai.