018 — Edit Distance

Source

• Original source: Classic Levenshtein distance DP exercise
• Platform: LeetCode — https://leetcode.com/problems/edit-distance/
• 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

1. Problem in simple words

দুটো string a আর b দেওয়া। তুমি a-কে b-তে রূপান্তর করতে চাও, তিন ধরনের একক-character operation ব্যবহার করে: একটা character insert করা, একটা character delete করা, বা একটা character replace করা। সবচেয়ে কম কয়টা operation-এ এটা করা যায়, সেটা বের করো।

a = "horse"
b = "ros"
সবচেয়ে ভালো: horse -> rorse (replace h->r)
            -> rose  (delete r)
            -> ros   (delete e)   = 3 operations

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") সরাসরি বসানো যায়।

6. Real-life analogy

ভাবো তুমি একটা typo-ভরা শব্দ ঠিক করছ। হাতে তিনটা key আছে: backspace (delete), একটা অক্ষর টাইপ করা (insert), আর একটা অক্ষরের উপর আরেকটা বসানো (replace)। প্রতিটা ধাপে যদি দুই শব্দের চলতি অক্ষর এক হয়, কোনো key চাপতে হয় না — এগিয়ে যাও বিনা খরচে; না হলে তিন key-র মধ্যে যেটা বাকি কাজ সবচেয়ে ছোট করে, সেটা চাপো।

7. Visual explanation

a = "cat", b = "cut"। Row = a-র prefix, column = b-র prefix:

        ""   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"। উত্তর নিচের-ডানের ঘরে।

8. Example input and output

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

9. Brute force thinking

প্রথম সরল চিন্তা: শেষ character দেখে তিন শাখায় recurse করো।

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:

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 একটা একক-অক্ষর সিদ্ধান্তে গুটিয়ে যায়।

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 — দুটোই ২. ✔

15. Python solution

# ---- 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।

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!।

18. Time complexity

তিন version-ই O(m·n) — প্রতিটা (i, j) জোড়া একবার গোনা হয়। (Naive recursion ছিল O(3^(m+n))।)

19. Space complexity

• Memoization: O(m·n) — cache + recursion stack।
• Tabulation: O(m·n) — পুরো 2D table।
• Fast version: O(n) — দুটো row।

20. Common mistakes

• base row/column ভুলে যাওয়া — dp[i][0] = i আর dp[0][j] = j না বসালে সব answer ছোট আসে।
• তিনটার মধ্যে diagonal বাদ দেওয়া (শুধু delete/insert রাখা) — তখন replace করা যায় না, distance অনেক বড় হয়ে যায়।
• match হলেও 1 + যোগ করা — match free, সেখানে খরচ নেই।

21. Which basic problem this inherits from

ভিত্তি: #17 LCS-এর two-prefix grid, mismatch-এ তিন-মুখী transition যোগ করে। ../state-transition-thinking.md-এর "Problem 7 — Edit Distance" section-এ ঠিক এই table আর transition বিস্তারিত আছে, আর ../patterns.md-এর "String DP" family এই grid-skeleton-এর কথা বলে।

22. Similar harder problems

• One Edit Distance (ঠিক এক edit দূরে কি না) — https://leetcode.com/problems/one-edit-distance/
• Delete Operation for Two Strings (শুধু delete) — https://leetcode.com/problems/delete-operation-for-two-strings/
• Regular Expression Matching (একই grid, ./* সহ) — https://leetcode.com/problems/regular-expression-matching/ (এই tracker-এর #22)

23. Pattern learned

Two-prefix string DP, three-way transition: dp[i][j] = দুই prefix-এর উত্তর; শেষ দুই character match হলে free diagonal, না হলে delete/insert/replace-এর 1 + min। এই তিন-মুখী কঙ্কাল alignment, spell-check, diff — সবখানে ফেরে।

24. Final summary

ভবিষ্যতের আমাকে: "Edit Distance = LCS-grid + তিন operation।" State dp[i][j] = a-র প্রথম i-কে b-র প্রথম j বানানোর min edit, transition match হলে diagonal নয়তো 1 + min(delete, insert, replace), base i/j। মনে রেখো: শেষ character-এ মনোযোগ দিলেই গোটা transformation একটা একক-অক্ষর সিদ্ধান্তে গুটিয়ে যায়।

25. JavaScript solution (with test cases)

Two-prefix 2D DP; match হলে free diagonal, নয়তো 1 + min(delete, insert, replace)। base row/column = i/j।

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)।

26. TypeScript solution (with test cases)

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<number>(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  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];
      } else {
        dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
      }
    }
  }
  return dp[m][n];
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
const cases: Array<[string, string, number]> = [
  ["horse", "ros", 3],
  ["intention", "execution", 5],
  ["cat", "cut", 1],
  ["", "abc", 3],
  ["abc", "", 3],
  ["abc", "abc", 0],
  ["ab", "ba", 2],
  ["sunday", "saturday", 3],
];
for (const [a, b, want] of cases) expect(editDistance(a, b), want, "edit");
console.log("সব TS test pass!");

TS টীকা: dp: number[][] ও new Array<number>(n+1) typing দিয়ে grid-এর element-type locked; return number (operation-সংখ্যা) স্পষ্ট। cases: Array<[string, string, number]> tuple-type দুই string ও expected জোড়া নিশ্চিত করে — ভুল arity বা type compile-time-এ ধরা পড়ে।

27. কোথায় কাজে লাগে (real-world use)

• Spell-check / autocorrect: ভুল বানান থেকে নিকটতম শব্দ বের করতে edit-distance (Levenshtein) র‍্যাঙ্কিং।
• diff / merge tools: দুই text-এর ন্যূনতম পরিবর্তন (insert/delete/replace) বের করে change-set তৈরি।
• DNA / sequence comparison: mutation distance মাপা (insert/delete/substitution)।
• Fuzzy search / record linkage: typo-সহিষ্ণু ম্যাচিং — কতটা edit-এ দুই string মেলে তা দিয়ে similarity।
• OCR / speech post-correction: চেনা শব্দভাণ্ডারের সাথে তুলনা করে আউটপুট সংশোধন।

মূল pattern: two-prefix dp[i][j], match হলে free diagonal নয়তো 1 + min(delete, insert, replace) — alignment/spell-check/diff সবখানে ফেরে।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।