Problem link ও উৎস
- **Original source:** Classic Levenshtein distance DP exercise
- **Platform:** LeetCode —
- **Topic:** dynamic programming (string DP)
- **Difficulty:** Hard
- **Pattern:** String DP (two-prefix grid, three-way transition)
- **Basic idea inherited from:** #17 Longest Common Subsequence — একই `dp[i][j]` grid, কিন্তু এখন তিনটা operation আর তাই তিন-মুখী transition
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো string `a` আর `b` দেওয়া। তুমি `a`-কে `b`-তে রূপান্তর করতে চাও, তিন ধরনের একক-character operation ব্যবহার করে: একটা character **insert** করা, একটা character **delete** করা, বা একটা character **replace** করা। সবচেয়ে কম কয়টা operation-এ এটা করা যায়, সেটা বের করো।
```text
a = "horse"
b = "ros"
সবচেয়ে ভালো: horse -> rorse (replace h->r)
-> rose (delete r)
-> ros (delete e) = 3 operations
```
### Input ও output {#8-example-input-and-output}
```text
Input : a = "horse", b = "ros" -> Output: 3
Input : a = "intention", b = "execution" -> Output: 5
Input : a = "cat", b = "cut" -> Output: 1 (replace)
Edge case 1: a = "", b = "abc" -> Output: 3 (সব insert)
Edge case 2: a = "abc", b = "" -> Output: 3 (সব delete)
Edge case 3: a = "abc", b = "abc" -> Output: 0
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একটা typo-ভরা শব্দ ঠিক করছ। হাতে তিনটা key আছে: backspace (delete), একটা অক্ষর টাইপ করা (insert), আর একটা অক্ষরের উপর আরেকটা বসানো (replace)। প্রতিটা ধাপে যদি দুই শব্দের চলতি অক্ষর এক হয়, কোনো key চাপতে হয় না — এগিয়ে যাও বিনা খরচে; না হলে তিন key-র মধ্যে যেটা বাকি কাজ সবচেয়ে ছোট করে, সেটা চাপো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি #17 LCS-এর two-prefix grid। সেখানে শেষ দুই character match কি না — তার উপর দুই-মুখী case ছিল। এখানে state একই (`dp[i][j]` = দুই prefix-এর উত্তর), কিন্তু mismatch হলে তিনটা পথ খোলা: delete, insert, replace — তাই transition তিন-মুখী `min`। LCS পেরোলে এটা শুধু "একটা শাখা বেশি"।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic শেষ character দুটোর তুলনা। `a[i-1] == b[j-1]` হলে শেষ character এমনিই মিলে গেছে — কোনো খরচ নেই, প্রশ্ন diagonal-এ ছোট হয় (`dp[i-1][j-1]`)। না মিললে তিনটার মধ্যে সস্তা একটা: `a`-র শেষ delete করো (`dp[i-1][j] + 1`), `a`-তে একটা insert করো `b`-র শেষ মেলাতে (`dp[i][j-1] + 1`), বা `a`-র শেষকে replace করো (`dp[i-1][j-1] + 1`)।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **2D array** `dp`, size `(m+1) x (n+1)` যেখানে `m = len(a)`, `n = len(b)`। `dp[i][j]` = `a`-র প্রথম `i` character-কে `b`-র প্রথম `j` character বানানোর min operation। প্রতিটা cell শুধু উপর, বাঁ আর diagonal cell পড়ে, তাই দুই rolling row-তে O(n) space-এও হয়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
State-এ দুটো স্বাধীন progress-সংখ্যা দরকার — `a`-তে কত character "ব্যবহার" করেছি, আর `b`-র কত character "তৈরি" করে ফেলেছি — কারণ শেষ operation নিতে দুটোই জানা লাগে। দুই-dimensional index ঠিক এই দুই সংখ্যা ধরে। padding row/column খালি prefix বোঝায়, যাতে base case ("সব insert" / "সব delete") সরাসরি বসানো যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: শেষ character দেখে তিন শাখায় recurse করো।
```text
edit(i, j): # a[0..i-1] -> b[0..j-1]-এর min ops
if i == 0: return j # সব insert
if j == 0: return i # সব delete
if a[i-1] == b[j-1]:
return edit(i-1, j-1) # free
return 1 + min(edit(i-1, j), # delete
edit(i, j-1), # insert
edit(i-1, j-1)) # replace
answer = edit(m, n)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
mismatch হলে প্রতিটা call তিনটা নতুন call জন্ম দেয়, তাই naive recursion **O(3^(m+n))** পর্যন্ত ফেটে যায়, আর একই `(i, j)` জোড়া অসংখ্যবার গোনা হয় (overlapping subproblems)। অথচ আলাদা `(i, j)` জোড়ার সংখ্যা মাত্র `(m+1) x (n+1)` — তাই memoize করলেই exponential কাজ polynomial হয়ে যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: উত্তর কেবল **দুই prefix-length** `(i, j)`-এর উপর নির্ভর করে — সেখানে পৌঁছাতে কী কী edit করেছিলাম, তাতে কিছু আসে যায় না। তাই প্রতিটা `(i, j)` একবার গুনে রাখলেই হয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `dp[i][j]` = `a`-র প্রথম `i`-টা character-কে `b`-র প্রথম `j`-টা character-এ রূপান্তর করার minimum operation-সংখ্যা।
**Transition:**
```text
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] # match -> free
else:
dp[i][j] = 1 + min(dp[i-1][j], # delete from a
dp[i][j-1], # insert into a
dp[i-1][j-1]) # replace
```
**Base case:** `dp[i][0] = i` (সব delete), `dp[0][j] = j` (সব insert), `dp[0][0] = 0`।
**Answer location:** `dp[m][n]`।
Tabulation: প্রথম row/column base value দিয়ে ভরো, তারপর row by row (`i = 1..m`), বাঁ থেকে ডানে (`j = 1..n`)। প্রতিটা cell-এর তিন dependency (উপর, বাঁ, diagonal) আগেই filled।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "পুরো string কীভাবে বদলাব" — এই বিশাল প্রশ্নের বদলে শুধু **শেষ character** নিয়ে ভাবো। শেষ দুই character এক হলে কাজ নেই, এক ধাপ ভেতরে ঢোকো; না হলে তিনটা একক operation-এর যেটা সবচেয়ে কম খরচে বাকি অংশ ছোট করে, সেটা নাও। গোটা transformation একটা একক-অক্ষর সিদ্ধান্তে গুটিয়ে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`a = "cat"`, `b = "cut"`। Row = `a`-র prefix, column = `b`-র prefix:
```text
"" c u t
"" 0 1 2 3
c 1 0 1 2
a 2 1 1 2
t 3 2 2 1 <- answer (replace 'a' -> 'u')
rule:
if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] (free, diagonal)
else: dp[i][j] = 1 + min(dp[i-1][j], (delete)
dp[i][j-1], (insert)
dp[i-1][j-1]) (replace)
```
প্রথম row "সব insert", প্রথম column "সব delete"। উত্তর নিচের-ডানের ঘরে।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`a = "ab"`, `b = "ba"`, 2D table (rows = `a`, cols = `b`):
1. base: `dp[0] = [0,1,2]`, `dp[i][0] = i`
2. i=1 (`a[0]='a'`): j=1 (`'b'`) mismatch → `1+min(dp[0][1], dp[1][0], dp[0][0]) = 1+min(1,1,0) = 1`; j=2 (`'a'`) match → `dp[0][1] = 1`
3. i=2 (`a[1]='b'`): j=1 (`'b'`) match → `dp[1][0] = 1`; j=2 (`'a'`) mismatch → `1+min(dp[1][2], dp[2][1], dp[1][1]) = 1+min(1,1,1) = 2`
4. `dp[2][2] = 2` → answer
হাতে মিলিয়ে: `"ab" -> "bb" (replace a->b) -> "ba" (replace b->a)`, ২ operation; অথবা insert+delete — দুটোই ২. ✔
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
# ---- way 1: memoization (top-down) ----
def edit_memo(a, b):
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(i, j): # a[0..i-1] -> b[0..j-1]
if i == 0:
return j
if j == 0:
return i
if a[i - 1] == b[j - 1]:
return solve(i - 1, j - 1)
return 1 + min(solve(i - 1, j), # delete
solve(i, j - 1), # insert
solve(i - 1, j - 1)) # replace
return solve(len(a), len(b))
# ---- way 2: tabulation (bottom-up, 2D) ----
def edit_tab(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j],
dp[i][j - 1],
dp[i - 1][j - 1])
return dp[m][n]
# ---- way 3: O(n) space (two rolling rows) ----
def edit_fast(a, b):
m, n = len(a), len(b)
prev = list(range(n + 1)) # dp[0][j] = j
for i in range(1, m + 1):
cur = [i] + [0] * n # cur[0] = i
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
prev = cur
return prev[n]
# ---- tests ----
cases = [
("horse", "ros", 3),
("intention", "execution", 5),
("cat", "cut", 1),
("", "abc", 3),
("abc", "", 3),
("abc", "abc", 0),
("ab", "ba", 2),
("sunday", "saturday", 3),
]
for a, b, want in cases:
assert edit_memo(a, b) == want, (a, b, edit_memo(a, b))
assert edit_tab(a, b) == want, (a, b, edit_tab(a, b))
assert edit_fast(a, b) == want, (a, b, edit_fast(a, b))
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `edit_memo`: `solve(i, j)` দুই prefix-এর min edit দেয়; খালি prefix হলে বাকি string-এর length ফেরত; match হলে free diagonal, নয়তো তিন operation-এর `1 + min`; `lru_cache` repeat এড়ায়।
- `edit_tab`: প্রথম column-এ `i` (সব delete), প্রথম row-এ `j` (সব insert) বসায়; তারপর nested loop প্রতিটা cell-এ transition প্রয়োগ করে; answer `dp[m][n]`।
- `edit_fast`: শুধু আগের row `prev` আর চলতি row `cur`; `cur[0]` প্রতিবার `i` দিয়ে শুরু (base column); `prev[j-1]` হলো diagonal।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ আটটা input: classic `"horse"/"ros"`, পাঠ্যবইয়ের `"intention"/"execution"` (5), single replace, দুই খালি-string edge (সব insert / সব delete), identical (0), `"ab"/"ba"` swap (2), আর `"sunday"/"saturday"` (3)। প্রতিটার জন্য তিন function-ই একই উত্তর দিতে হবে। সব pass হলে শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
Two-prefix 2D DP; match হলে free diagonal, নয়তো `1 + min(delete, insert, replace)`। base row/column = i/j।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// dp[i][j] = a-র প্রথম i-কে b-র প্রথম j বানানোর min operation
function editDistance(a, b) {
const m = a.length, n = b.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) dp[i][0] = i; // সব delete
for (let j = 0; j <= n; j++) dp[0][j] = j; // সব insert
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]; // match -> free
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j], // delete from a
dp[i][j - 1], // insert into a
dp[i - 1][j - 1] // replace
);
}
}
}
return dp[m][n];
}
// ---- test cases (example + edge) ----
const cases = [
["horse", "ros", 3],
["intention", "execution", 5],
["cat", "cut", 1], // replace
["", "abc", 3], // সব insert
["abc", "", 3], // সব delete
["abc", "abc", 0],
["ab", "ba", 2],
["sunday", "saturday", 3],
];
for (const [a, b, want] of cases) {
assert(editDistance(a, b) === want, "edit " + a + "/" + b);
}
console.log("সব JS test pass!");
```
> **JS টীকা:** 2D DP grid বানাতে `Array.from({length: m+1}, () => new Array(n+1).fill(0))` — `.fill()` দিয়ে এক shared row reuse কোরো না। base row/column ভুলে গেলে (`dp[i][0]=i`, `dp[0][j]=j`) সব answer ছোট আসে। `Math.min(a, b, c)` তিন argument নেয় (Python-এর `min(a,b,c)`-এর মতো); match হলে `1+` দিও না (free)।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function editDistance(a: string, b: string): number {
const m: number = a.length, n: number = b.length;
const dp: number[][] = Array.from({ length: m + 1 }, () => new Array