DP problems — edit distance (Levenshtein): Question bank

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

Shuru karne se pehle, parent ke teen arrows apne dimag mein rakho:

↖ diagonal = current characters ko compare karo (free agar equal hain, $+ 1$ agar substitute kar rahe ho),
↑ up = $A$ ka ek character delete karo,
← left = $B$ ka ek character insert karo.

Neeche sab kuch usi picture ka stress-test hai.

True or false — justify karo

The min-of-three rule hamesha apply hoti hai, chahe characters match karein.

False. Match hone par tum pure diagonal

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

lete ho bina $+ 1$ ke; min-of-three ko force karne se ek stray

+ 1

path jeet sakta hai aur distance over-count ho jaata hai.

Edit distance string lengths ke difference ke barabar hoti hai.

False. Length difference sirf ek lower bound hai:

k

ka length gap

k

se kam insert/delete moves mein fix nahi ho sakta, lekin substitutions tab bhi cost add karte hain jab lengths equal hon (e.g. "cat" → "dog" 3 hai, 0 nahi).

Edit distance symmetric hai:

d (A, B) = d (B, A)

True.

A

mein har insert

B

se ek delete hai aur vice-versa, aur substitution apna khud ka inverse hai — isliye koi bhi optimal edit script usi cost par reverse hota hai.

Agar do strings equal hain, toh unki edit distance 0 hai.

True. Har character match karta hai, isliye diagonal

d p [m] [n]

tak 0 carry karta hai; koi bhi operation kabhi force nahi hota.

d p [i] [j]

characters A[i] aur B[j] ko compare karta hai.

False.

d p [i] [j]

pehle $i$ aur pehle $j$ characters ko cover karta hai, isliye current characters 0-indexed A[i-1] aur B[j-1] hain. Ye off-by-one sabse common bug hai.

Table fill karne ka order matter nahi karta.

False. Ek cell apne up, left, aur up-left neighbours padhta hai, isliye woh pehle se filled hone chahiye — row-by-row (ya column-by-column) top-left se bottom-right zaroori hai.

Edit distance triangle inequality follow karta hai:

d (A, C) \leq d (A, B) + d (B, C)

True. Tum hamesha

A \to B

phir

B \to C

convert kar sakte ho; wo combined script sum cost karti hai, isliye optimal

A \to C

cost usse badi nahi ho sakti. Ye Levenshtein ko ek saccha metric banata hai.

Empty string ka kisi bhi string se well-defined edit distance hota hai.

True.

d ("", B) = ∣ B ∣

(har char insert karo) aur

d (A, "") = ∣ A ∣

(har char delete karo) — ye exactly base row aur column hain.

Substitutions allow karna kabhi bhi insert+delete-only model se answer bada nahi kar sakta.

True. Ek substitution 1 cost karti hai lekin ek delete-then-insert pair replace karti hai jo 2 cost karta, isliye iska available hona total ko sirf lower (ya equal) karta hai.

Error dhundho

"Maine A[i-1] != B[j-1] ke liye dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) likha (koi +1 nahi)."

Error:

+ 1

missing hai. Mismatch ek edit force karta hai, isliye ye

1 + min (\dots)

hona chahiye; iske bina table flat rehti hai aur impossibly small distances report karta hai.

"Maine poori table ko 0 se initialise kiya, phir double loop chalaya."

Error: row 0 mein

d p [0] [j] = j

aur column 0 mein

d p [i] [0] = i

hona chahiye, 0 nahi. Unhe 0 par chhod dene se recurrence false "free" prefixes padh leta hai aur undercount karta hai.

"Match par maine dp[i][j] = 1 + dp[i-1][j-1] kiya."

Error: match par us position ke liye koi cost nahi hoti; ye dp[i][j] = dp[i-1][j-1] hona chahiye bina

+ 1

ke. 1 add karna har aligned character ko inflate karta hai.

"Delete left cell dp[i][j-1] se aata hai."

Error:

A

-se-delete upar se aata hai,

d p [i - 1] [j]

(shorter

A

, same

B

). Left cell

d p [i] [j - 1]

insert move hai.

"Maine sirf do neighbours (up aur left) use kiye kyunki substitution sirf delete + insert hai."

Error: diagonal drop karne se 1-cost substitution aur free match choot jaata hai; tum ek alag distance compute karte (insert/delete-only variant), jo strictly bada ho sakta hai.

"Space bachane ke liye maine sirf previous column rakha lekin row by row iterate kiya."

Error: agar tum row by row sweep karo toh tumhe previous row chahiye (aur ek running left value). Column rakhte hue rows mein iterate karna stale data padhta hai — rakha hua array sweep direction se match karna chahiye.

Why questions

Recurrence har prefix ke sirf last character ko kyun inspect karta hai?

Koi bhi edit script jo A[0..i) ko B[0..j) mein fix karta hai, final position ke baare mein exactly ek kaam karta hai; use fix karna ek character peel karta hai aur ek strictly chota edit-distance problem chhod deta hai jo tumne pehle se solve kar liya — yahi Optimal Substructure hai.

DP plain recursion se faster kyun hai?

Naive recursion same prefix pairs ko exponentially baar recompute karta hai; ye Overlapping Subproblems hain, isliye har

d p [i] [j]

ko ek baar cache karna exponential time ko

O (mn)

mein badal deta hai — dekho Recursion and Memoization.

Long common subsequences distance ko small kyun banate hain?

Har matching character diagonal par free pass ho jaata hai, isliye cost sirf un positions par aati hai jo shared alignment ke bahar hain — yahi reason hai ki edit distance Longest Common Subsequence se gehri tarah judi hai.

Space ko

O (min (m, n))

tak kyun reduce kar sakte hain?

Ek cell sirf row

i - 1

aur column

j - 1

padhta hai, isliye humein purani rows ki zarurat nahi; ek previous row rakhna (shorter string ko row dimension choose karke) kaafi hai — ye Space Optimization in DP hai.

Candidate moves par minimum kyun lete hain sum ki jagah?

Har candidate last move ke liye ek alag complete strategy hai, aur hum sabse sasta ek chahte hain — hum ek path choose karte hain, sabhi perform nahi karte, isliye ye min hai, sum nahi.

Final answer

d p [m] [n]

(bottom-right) kyun hai aur

d p [0] [0]

kyun nahi?

d p [i] [j]

prefix length ke saath badhta hai;

d p [m] [n]

poori strings use karta hai, jabki

d p [0] [0] = 0

sirf trivial "two empty strings" seed hai jisse table shuru hoti hai.

Edge cases

d (A, B)

kya hoga jab

A

empty ho?

∣ B ∣

hai: tumhe

B

ka har character insert karna hoga, aur kuch bhi sasta nahi hai — ye exactly base row

d p [0] [j] = j

hai.

d (A, B)

kya hoga jab dono strings empty hon?

0. Do empty strings ko koi edit nahi chahiye, jo corner seed

d p [0] [0] = 0

deta hai.

Length

n

ki do identical strings ke beech edit distance kya hai?

n

chahe kuch bhi ho: har character match karta hai isliye diagonal

d p [n] [n]

tak 0 carry karta hai.

Length

m

aur

n

ki strings ke beech maximum possible edit distance kya hai?

max (m, n)

: worst case mein tum overlapping

min (m, n)

positions substitute karte ho aur remaining

∣ m - n ∣

insert/delete karte ho, aur tumhe kabhi

max (m, n)

se zyada moves ki zarurat nahi.

Do same-length strings ke beech distance kya hai jo kisi bhi position par koi character share nahi karte?

Exactly unki common length: har position mismatch karta hai aur ek substitution se fix ho sakta hai, aur koi insert/delete use nahi kar sakta kyunki lengths pehle se same hain.

Agar

B

A

ka prefix hai (e.g. "apple" → "app"), toh distance kya hai?

Length gap

∣ A ∣ - ∣ B ∣

: saare shared characters free align ho jaate hain aur tum sirf

A

ke trailing extras delete karte ho.

Agar

B

A

mein ek extra character somewhere insert karke bana hai, toh distance kya hai?

1 — ek single insertion kaafi hai, aur length difference kam se kam 1 force karta hai, isliye ye exactly 1 hai.

Agar tum swap karo ki kaun si string rows hai aur kaun si columns, toh answer par kya asar hoga?

Kuch nahi — distance symmetric hai, isliye table transpose hoti hai lekin

d p [m] [n]

unchanged rehta hai; sirf delete/insert ke labels arrows par swap ho jaate hain.

Connections

Parent — recurrence, base cases, aur worked tables jo ye traps stress-test karte hain.
Dynamic Programming, Optimal Substructure, Overlapping Subproblems — ye machinery hai "why a recurrence exists" ke peeche.
Recursion and Memoization, Space Optimization in DP — implementation trade-offs jo upar probe kiye gaye.
Longest Common Subsequence, Sequence Alignment — jahan "shared subsequences are free" aage le jaata hai.