DP problems — edit distance (Levenshtein): Foundations

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

Yeh page kuch bhi assume nahi karta. Parent note Edit Distance padhne se pehle, usmein aane wale har symbol par aapki pakad honi chahiye. Hum har ek ko — pehle meaning, phir picture, phir kyun yeh topic isko use karta hai — ek aise order mein build karte hain jahaan har cheez pichhli cheez par tiki ho.

0. What is a "string"?

Motiyon ki tasveer:

Yeh topic kyun isko zaroori samajhta hai: edit distance ek sawaal hai do strings ke baare mein — kitne single-bead changes ek row of beads ko doosre mein badal dete hain. Aage ka sabkuch inhi do taaon ki comparison ke baare mein hai.

1. Indexing — pointing at one bead

Yeh topic kyun isko zaroori samajhta hai: topic baar baar "A ke current last character" aur "B ke current last character" ki comparison karta hai. Hume in characters ki taraf point karne ka ek precise tarika chahiye. Woh pointer ek index hai.

2. Prefix — a beginning slice of the string

A = "horse" ke liye examples:

notation	matlab	value
`A[0..0)`	pehle 0 chars	`""` (empty!)
`A[0..1)`	pehla 1 char	`"h"`
`A[0..3)`	pehle 3 chars	`"hor"`
`A[0..5)`	pehle 5 chars	`"horse"`

Yeh topic kyun isko zaroori samajhta hai: do prefixes ke beech ki edit distance usi sawaal ka genuinely chhota instance hai. Woh "same sawaal, chhota size" ki property hi hai jo recursion aur Dynamic Programming ko possible banati hai — dekho Optimal Substructure.

3. The empty string `""`

Yeh topic kyun isko zaroori samajhta hai: yeh sabse chhota possible starting point hai. Ek khaali taar ko "ros" mein badalne ke liye aap sirf moti add kar sakte hain, toh cost obvious hai (3 inserts). Yeh obvious cases hi base cases hain jinpar poori grid anchored hai. Empty string ke bina, upar build karne ka koi floor nahi hai.

4. The three edit operations

Yeh topic kyun isko zaroori samajhta hai: "edit distance" hi in coins ki count hai. Moves aur unki price define karna (sab 1) game ki rulebook hai. Agar substitution ki cost 1 ki jagah 2 hoti, toh poora table badal jaata — isliye cost model pehle batana zaroori hai.

5. The subscript pair $(i, j)$ and the table `dp[i][j]`

"+1" kyun? Kyunki $i = 0$ aur $j = 0$ ka matlab empty prefixes hai, aur woh step 3 ke base cases hain. Unhe hold karne ke liye ek row aur column chahiye.

Yeh topic kyun isko zaroori samajhta hai: poori method hai "har box fill karo, phir bottom-right box dp[m][n] padho." Table answer store hai. Pair $(i, j)$ har answer ka address hai.

6. Base cases — woh boxes jo aap kisi bhi rule se pehle fill karte hain

Grid apne aap se fill nahi ho sakta: bilkul pehla box, aur poori top row aur left column, pehle haath se likhni padti hai. Inhe starting values ko base cases kehte hain.

Yeh topic kyun isko zaroori samajhta hai: baaki har box unse upar aur baayein ke boxes se compute hoga. Agar top row aur left column pehle fill nahi hain, toh woh look-ups khaale boxes padhenge aur poori grid collapse ho jaayegi. Base cases woh floor hain jis par sab kuch khada hai.

7. `min` — sabse sasta option choose karna

Yeh tool kyun aur koi nahi? Har box par pahunchne ke kai tarike hain (delete, insert, substitute). Har tarike ki coin cost hai. Hum kam se kam coins chahte hain, toh hum options compare karte hain aur sabse chhota rakhte hain — exactly yahi \min karta hai. Hum yahan \max kabhi use nahi karte kyunki zyada coins bura hai, behtar nahi.

8. "Recurrence" — chhote jawabon par lean karne wale rule ke liye word

Yeh topic kyun is word ko zaroori samajhta hai: parent note main formula ko "the recurrence" / "the transition" kehta hai. Ab aap jaante hain iska matlab sirf "woh rule jo ek box ko chhote boxes se fill karta hai." Kuch scary nahi.

9. Putting the notation together

Ab parent ke rule ka har symbol earn ho chuka hai. Dhyan dijiye — do cases hain — ek match (freebie) aur ek mismatch (coin do) — isliye rule ko bade curly brace ke saath piecewise likha gaya hai:

Formula Recurrence — piecewise, taaki freebie diagonal clear ho

d p [i] [j] = ⎩ ⎨ ⎧ d p [i - 1] [j - 1], 1 + min (substitute d p [i - 1] [j - 1], delete d p [i - 1] [j], insert d p [i] [j - 1]), A [i - 1] = B [j - 1] (match: no coin) A [i - 1] \neq = B [j - 1]

$d p [i - 1] [j - 1]$ = box diagonally upar-baayein: dono prefixes ek moti chhote.
$d p [i - 1] [j]$ = box seedha upar: A ka prefix ek chhota (humne A ka aakhri moti hataya → delete).
$d p [i] [j - 1]$ = box seedha baayein: B ka prefix ek chhota (B ko ek moti chahiye tha jo hamare paas nahi tha → insert).
1 + = woh coin jo hum tab kharach karte hain jab koi move karna padta hai.
Top case (match): current moti already equal hain, toh is position ko koi edit nahi chahiye — hum sirf diagonal dp[i-1][j-1] bina +1 ke copy karte hain. Yahi woh "freebie" hai jiske baare mein parent note warn karta hai; yahan 1 add karna over-count hoga.
Bottom case (mismatch): moti alag hain, toh hume 1 coin dena hi padega, aur hum \min se teen arrivals mein sabse sasta choose karte hain.

Ab parent note ki har cheez padhne layak hai, kyunki aap A[i-1], A[0..i), dp[i][j], base cases, \min, aur "recurrence" ko ek ek symbol karke decode kar sakte hain.

The prerequisite map

Har foundation upar recurrence mein flow karta hai, jo poore topic mein flow karta hai. Related vault ideas — Recursion and Memoization, Overlapping Subproblems, Optimal Substructure, Longest Common Subsequence, aur Sequence Alignment — sab isi "table of prefix answers" machinery ko reuse karte hain, aur Space Optimization in DP table ko shrink karta hai jab aap ise samajh lete hain.

Equipment checklist

Apne aap ko test karo — sirf tab reveal karo jab aap zor se jawab de chuke ho.

String kya hoti hai aur uski length kya hoti hai?

Characters ki ek left-to-right row; length = usme kitne characters hain.

A = "horse" ke liye, A[0] kya hai aur A[4] kya hai?

A[0] hai 'h'; A[4] hai 'e' (indexing 0 se start hoti hai).

Length-5 string ka aakhri index 4 kyun hai, 5 kyun nahi?

Kyunki hum positions 0 se count karte hain, toh sabse bada valid index length − 1 hota hai.

Prefix A[0..i) mein kya hota hai?

A ke pehle i characters, position i se ek kadam pehle rukke.

A[0..0) kya hai?

Empty string "" — zero characters.

Teen edit operations kya hain aur unki costs kya hain?

Insert, delete, substitute — har ek ki cost 1; match ki cost 0.

dp[i][j] kya store karta hai?

A ke pehle i chars aur B ke pehle j chars ke beech ki minimum edit distance.

Table mein m+1 rows aur n+1 columns kyun hote hain?

Extra row/column empty-prefix base cases hold karte hain (i=0 aur j=0).

Teen base cases state karo.

dp[0][0]=0; dp[i][0]=i i>0 ke liye (sab delete); dp[0][j]=j j>0 ke liye (sab insert).

\min(a,b,c) kya compute karta hai aur yahan kyun use hota hai?

Sabse chhoti value; hum kam se kam coins chahte hain, toh hum sabse sasta arrival option choose karte hain.

"Recurrence relation" kya hoti hai?

Ek aisa rule jo ek jawab ko usi problem ke chhote versions ke jawabon se compute karta hai.

Match A[i-1]==B[j-1] par rule kya karta hai?

Diagonal dp[i-1][j-1] ko bina +1 ke copy karta hai (freebie).

Kaun sa neighbouring box "delete" hai, kaun sa "insert" hai?

Upar (dp[i-1][j]) = A se delete; baayein (dp[i][j-1]) = A mein insert.