কনটেন্টে যান

021 — Word Ladder

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • Original source: Implicit graph-এ shortest-path-এর classic প্রয়োগ
  • Platform: LeetCode — https://leetcode.com/problems/word-ladder/
  • Topic: graphs
  • Difficulty: Hard
  • Pattern: BFS on implicit graph (word = node, এক-অক্ষর-আলাদা = edge)
  • Basic idea inherited from: BFS levels (এই tracker-এর BFS গুচ্ছ) + hashing (../../05-hashing/)

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তোমাকে একটা begin_word, একটা end_word, আর একগুচ্ছ word-এর list দেওয়া আছে। তুমি প্রতি ধাপে একটা word-এর ঠিক একটা অক্ষর বদলাতে পারো, কিন্তু শর্ত — বদলানোর পর যে নতুন word তৈরি হয়, সেটা list-এর মধ্যে থাকতে হবে। begin_word থেকে শুরু করে end_word-এ পৌঁছাতে সবচেয়ে ছোট transformation sequence-এ কয়টা word থাকে (begin আর end সহ), সেটা বের করো। পৌঁছানো না গেলে 0।

উদাহরণ
begin = "hit", end = "cog"
list  = hot, dot, dog, lot, log, cog

hit -> hot -> dot -> dog -> cog      5 টা word (সবচেয়ে ছোট)
উত্তর: 5

Input ও output

উদাহরণ
Input : begin="hit", end="cog", list=[hot,dot,dog,lot,log,cog]
Output: 5

Input : begin="hit", end="cog", list=[hot,dot,dog,lot,log]   (cog নেই)
Output: 0

Edge case (একধাপেই end): begin="hot", end="dog", list=[hot,dog,dot] -> 3
Edge case (begin==end, list-এ আছে): begin="hit", end="hit", list=[hit] -> 1

চেনা উদাহরণে বোঝা

ভাবো প্রতিটা word একটা শহর, আর দুটো শহরের মধ্যে সরাসরি রাস্তা আছে কেবল যদি তাদের নামে ঠিক একটা অক্ষর আলাদা হয়। তুমি hit শহর থেকে cog শহরে যেতে চাও, সবচেয়ে কম শহর ছুঁয়ে। তুমি তো সব রাস্তার ম্যাপ হাতে পাওনি — কিন্তু নিয়ম জানো (এক অক্ষর আলাদা)। তাই তুমি ঢেউয়ের মতো ছড়াও: এক ধাপে যত শহরে যাওয়া যায় সব ছোঁও, তারপর তাদের থেকে পরের ধাপ — যেদিন cog ছোঁবে, সেই ধাপ-সংখ্যাই সবচেয়ে ছোট পথ।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা দাঁড়িয়ে BFS-এর "shortest path in unweighted graph" ধারণার উপর (এই tracker-এর BFS গুচ্ছ, যেমন Rotting Oranges/Labyrinth)। মূল মোচড়: এখানে graph টা তোমাকে কেউ দেয়নি — তুমি নিজে বানাবে মাথায়। প্রতিটা word একটা node, আর দুটো word-এর মধ্যে edge আছে যদি তারা ঠিক একটা অক্ষরে আলাদা হয়। সব edge-এর "ওজন" সমান (এক ধাপ), তাই BFS-ই সবচেয়ে ছোট sequence দেয়। সাথে ../../05-hashing/-এর set/dict লাগে দ্রুত lookup-এর জন্য।

ভেতরের যুক্তি

লুকানো logic দুই স্তরে। প্রথমত, "এক অক্ষর আলাদা" সম্পর্কটাই একটা implicit graph সংজ্ঞায়িত করে — edge গুলো explicit list নয়, একটা নিয়ম। দ্বিতীয়ত, neighbor খোঁজার চালাকি: প্রতিটা word-এর প্রতিটা position-এ অক্ষরটা * দিয়ে ঢেকে একটা pattern বানাও (যেমন hot → *ot, h*t, ho*)। একই pattern-এর সব word পরস্পরের neighbor। এই bucket-trick neighbor খোঁজাকে প্রতিবার পুরো list scan (O(N·L)) থেকে নামিয়ে আনে — কারণ "এক অক্ষর বদলালে কে কে হয়" আগেই group করা থাকে।

কী দিয়ে তথ্য রাখব

তিনটা জিনিস: (১) একটা deque — BFS-এর FIFO queue, layer-by-layer expand করতে; (২) word-list-এর একটা set — কোনো word valid কিনা O(1)-তে check করতে; (৩) একটা dict (defaultdict) — pattern → ওই pattern মেলানো word-দের list, অর্থাৎ implicit graph-এর adjacency।

এটি কেন উপযুক্ত

Deque fit করে কারণ unweighted graph-এ সবচেয়ে ছোট path মানে BFS, আর BFS-এর প্রাণ FIFO queue — যে word আগে discover হয় তার distance ছোট, তাই আগে process হওয়া দরকার। Set fit করে কারণ "এই বানানো word কি list-এ আছে" প্রশ্নটা লক্ষবার আসে; list-এ in হলে O(N), set-এ O(1)। Pattern-dict fit করে কারণ প্রতিটা node-এর neighbor বারবার লাগে, আর bucket আগে বানিয়ে রাখলে neighbor lookup প্রায় constant।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: explicit graph বানাও — প্রতি জোড়া word তুলনা করে দেখো তারা এক অক্ষরে আলাদা কিনা, হলে edge যোগ করো। তারপর সেই graph-এ সাধারণ BFS চালিয়ে begin থেকে end-এর দূরত্ব বের করো।

উদাহরণ
1) প্রতি জোড়া (wi, wj)-এর জন্য: এক অক্ষর আলাদা হলে edge
2) তৈরি graph-এ BFS begin থেকে
3) end-এর level = উত্তর

কোথায় বেশি কাজ হচ্ছে

সব জোড়া তুলনা করতে O(N^2) জোড়া, আর প্রতি জোড়ায় অক্ষর মেলাতে O(L) — মোট O(N^2 · L), যেখানে N = word সংখ্যা, L = word দৈর্ঘ্য। N বড় হলে এটা ভয়ংকর ধীর। আসল অপচয়: আমরা প্রতিটা সম্ভাব্য জোড়া যাচাই করছি, অথচ neighbor আসলে অল্প — pattern-bucket দিয়ে সরাসরি "এক অক্ষর বদলালে কে হয়" বের করা যায়, সব জোড়া দেখা লাগে না।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: graph explicit-ভাবে বানানোই দরকার নেই। দুটো word neighbor কিনা সেটা একটা নিয়ম — আর নিয়মটা bucket দিয়ে দ্রুত প্রয়োগ করা যায়: একই *-pattern মেলানো সব word পরস্পরের neighbor। তাই BFS চলাকালীন on-the-fly neighbor বের করা সম্ভব, পুরো O(N^2) adjacency matrix ছাড়াই।

আরও কম কাজে সমাধান

আগে একবার ঘুরে প্রতিটা word-এর প্রতিটা position-এর pattern বানিয়ে dict-এ জমাও (*ot, h*t, ...)। এরপর BFS: queue থেকে word বের করো, তার প্রতিটা position-এ * বসিয়ে pattern বানাও, সেই bucket-এর যত unvisited word আছে সব queue-তে দাও (steps+1 সহ)। end প্রথমবার queue থেকে বেরোলে — বা push হওয়ার সময় check করলে — সেই steps-ই সবচেয়ে ছোট, কারণ BFS layer-by-layer ছড়ায়।

ভাবনার পরিবর্তন

মোচড়: "graph তো দেওয়া নেই" দেখে থেমো না — জিজ্ঞেস করো "node কী, আর edge-এর নিয়ম কী?" এখানে node = word, edge = এক-অক্ষর-আলাদা। graph-টা মাথায় বানিয়ে নিলেই Hard problem-টা চেনা BFS-এ মিলিয়ে যায়। (../shortest-path.md-এর শেষ row: unweighted → plain BFS, deque।)

ছবিতে বোঝা

begin="hit" থেকে BFS-এর layer, (word, steps):

উদাহরণ
Layer 1:  hit (1)
  h*t,  *it,  hi*  pattern দেখি -> hot মেলে
Layer 2:  hot (2)
  *ot -> dot, lot ;  ho* -> (নতুন নেই)
Layer 3:  dot (3)  lot (3)
  dot: d*t->(নেই)  do*->dog ;  lot: lo*->log
Layer 4:  dog (4)  log (4)
  dog: *og->cog, log(visited)  ;  log: *og->cog
Layer 5:  cog (5)   <- end পেলাম, return 5

ছোট input-এ ধাপে ধাপে

ছোট input begin="a", end="c", list=["a","b","c"] (উত্তর 2):

  1. bucket বানাই: "*" → [a, b, c] (প্রতিটা এক-অক্ষর word-এর pattern *)।
  2. visited={a}, queue [(a, 1)]।
  3. pop (a, 1)। a == c? না। pattern "*"-এর bucket [a,b,c]: b unvisited → push (b,2); c unvisited → push (c,2)। queue [(b,2),(c,2)]।
  4. pop (b, 2)। b == c? না। "*"-এর word সব visited, নতুন কিছু না।
  5. pop (c, 2)। c == c? হ্যাঁ → return 2।

কোড ও ব্যাখ্যা

Python

Python
from collections import defaultdict, deque

def word_ladder(begin_word, end_word, word_list):
    # BFS on implicit graph: প্রতিটা word একটা node, এক-অক্ষর-আলাদা হলে edge
    words = set(word_list)
    if end_word not in words:
        return 0
    # pattern bucket: "h*t" -> [hot, hat, ...] দিয়ে neighbor O(1)-এ খুঁজি
    buckets = defaultdict(list)
    for w in words:
        for i in range(len(w)):
            buckets[w[:i] + "*" + w[i + 1:]].append(w)
    visited = {begin_word}
    queue = deque([(begin_word, 1)])         # (word, এই word পর্যন্ত sequence দৈর্ঘ্য)
    while queue:
        word, steps = queue.popleft()
        if word == end_word:
            return steps
        for i in range(len(word)):
            pattern = word[:i] + "*" + word[i + 1:]
            for nxt in buckets[pattern]:
                if nxt not in visited:
                    visited.add(nxt)
                    queue.append((nxt, steps + 1))
    return 0

# ---- tests ----
assert word_ladder("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]) == 5
assert word_ladder("hit", "cog", ["hot", "dot", "dog", "lot", "log"]) == 0
assert word_ladder("a", "c", ["a", "b", "c"]) == 2
assert word_ladder("hot", "dog", ["hot", "dog", "dot"]) == 3
assert word_ladder("hit", "hit", ["hit"]) == 1
print("সব test pass!")

কোডের প্রতিটি অংশ

  • words = set(word_list) — list-কে set বানাই, যাতে membership check O(1) হয়।
  • if end_word not in words: return 0 — গন্তব্য word-ই list-এ না থাকলে কখনো পৌঁছানো যাবে না।
  • buckets[w[:i]+"*"+w[i+1:]].append(w) — প্রতিটা word-এর প্রতি position-এ * বসিয়ে pattern, একই pattern-এর word-রা neighbor।
  • visited = {begin_word} — একই word দুবার queue-তে না দিতে; BFS-এ প্রথম discovery-ই সবচেয়ে ছোট দূরত্ব।
  • queue = deque([(begin_word, 1)]) — start word, sequence-এ এ পর্যন্ত 1 টা word।
  • if word == end_word: return steps — end প্রথমবার pop হলেই sequence সবচেয়ে ছোট, return।
  • ভেতরের loop — current word-এর প্রতিটা pattern-এর bucket ঘেঁটে unvisited neighbor queue-তে দেয় steps+1 সহ।

Output মিলিয়ে দেখা

word_ladder("hit","cog",[hot,dot,dog,lot,log,cog]): cog list-এ আছে, তাই চলবে। BFS layer 1-এ hit, layer 2-এ hot, layer 3-এ dot,lot, layer 4-এ dog,log, layer 5-এ cog। cog pop হয় steps=5 নিয়ে → return 5। দ্বিতীয় test-এ cog নেই, তাই শুরুতেই return 0। বাকি assert pass, শেষে print: সব test pass!।

JavaScript ও test cases

implicit graph-এ BFS: word = node, *-pattern bucket দিয়ে neighbor; Set দ্রুত lookup, Map bucket।

JavaScript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// begin থেকে end পর্যন্ত সবচেয়ে ছোট transformation sequence-এর দৈর্ঘ্য (begin+end সহ)
function wordLadder(beginWord, endWord, wordList) {
  const words = new Set(wordList);
  if (!words.has(endWord)) return 0;
  // pattern bucket: "h*t" -> [hot, hat, ...] দিয়ে neighbor দ্রুত খুঁজি
  const buckets = new Map();
  for (const w of words) {
    for (let i = 0; i < w.length; i++) {
      const pat = w.slice(0, i) + "*" + w.slice(i + 1);
      if (!buckets.has(pat)) buckets.set(pat, []);   // shared-ref এড়িয়ে নতুন array
      buckets.get(pat).push(w);
    }
  }
  const visited = new Set([beginWord]);
  const queue = [[beginWord, 1]];                    // [word, sequence দৈর্ঘ্য]
  let head = 0;
  while (head < queue.length) {
    const [word, steps] = queue[head++];
    if (word === endWord) return steps;
    for (let i = 0; i < word.length; i++) {
      const pat = word.slice(0, i) + "*" + word.slice(i + 1);
      for (const nxt of buckets.get(pat) || []) {
        if (!visited.has(nxt)) {
          visited.add(nxt);                          // push-এই mark
          queue.push([nxt, steps + 1]);
        }
      }
    }
  }
  return 0;
}
// ---- test cases (example + edge) ----
assert(wordLadder("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]) === 5, "classic");
assert(wordLadder("hit", "cog", ["hot", "dot", "dog", "lot", "log"]) === 0, "no-end");   // edge
assert(wordLadder("a", "c", ["a", "b", "c"]) === 2, "single-char");
assert(wordLadder("hot", "dog", ["hot", "dog", "dot"]) === 3, "three");
assert(wordLadder("hit", "hit", ["hit"]) === 1, "begin==end");
console.log("সব JS test pass!");

JS টীকা: Map of arrays বানানোর সময় প্রতিটা নতুন key-তে buckets.set(pat, []) দিয়ে আলাদা array দাও — একই shared array reuse করলে সব pattern একসাথে দূষিত হতো। Set membership O(1), array-তে includes O(n) — তাই words/visited দুটোই Set। array-as-queue-তে shift() এড়িয়ে head index, নাহলে BFS ধীর।

TypeScript ও test cases

TypeScript
function wordLadder(beginWord: string, endWord: string, wordList: string[]): number {
  const words: Set<string> = new Set(wordList);
  if (!words.has(endWord)) return 0;
  const buckets: Map<string, string[]> = new Map();
  for (const w of words) {
    for (let i = 0; i < w.length; i++) {
      const pat: string = w.slice(0, i) + "*" + w.slice(i + 1);
      if (!buckets.has(pat)) buckets.set(pat, []);
      (buckets.get(pat) as string[]).push(w);
    }
  }
  const visited: Set<string> = new Set([beginWord]);
  const queue: Array<[string, number]> = [[beginWord, 1]];
  let head = 0;
  while (head < queue.length) {
    const [word, steps] = queue[head++];
    if (word === endWord) return steps;
    for (let i = 0; i < word.length; i++) {
      const pat: string = word.slice(0, i) + "*" + word.slice(i + 1);
      for (const nxt of buckets.get(pat) ?? []) {
        if (!visited.has(nxt)) {
          visited.add(nxt);
          queue.push([nxt, steps + 1]);
        }
      }
    }
  }
  return 0;
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(wordLadder("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]), 5, "classic");
expect(wordLadder("hit", "cog", ["hot", "dot", "dog", "lot", "log"]), 0, "no-end");
expect(wordLadder("a", "c", ["a", "b", "c"]), 2, "single");
console.log("সব TS test pass!");

TS টীকা: queue-কে Array<[string, number]> (tuple) declare করায় প্রতিটা entry-তে word আর steps-এর type locked — destructure-এ word: string, steps: number আপনাআপনি; Map<string, string[]> bucket-এর key ও value type পরিষ্কার। ?? [] (nullish coalescing) দিয়ে Map.get-এর undefined নিরাপদে সামলানো।

খরচ ও সাধারণ ভুল

সময়

O(N · L^2) — N = word সংখ্যা, L = word দৈর্ঘ্য। প্রতিটা word-এর জন্য L টা pattern বানাই, প্রতিটা pattern বানাতে slicing-এ O(L), তাই N·L·L। BFS-এ প্রতিটা word একবার process, neighbor lookup bucket থেকে।

অতিরিক্ত জায়গা

O(N · L^2) — bucket dict-এ প্রতিটা word L টা pattern-এ যোগ হয়, প্রতিটা pattern key দৈর্ঘ্য L; সাথে visited set আর queue-তে O(N) word।

যে ভুলগুলো এড়াতে হবে

  • explicit O(N^2) adjacency বানানো — N বড় হলে TLE; pattern-bucket দিয়ে এড়াও।
  • visited-এ word যোগ করা pop-এর সময়, push-এর সময় নয় — তখন একই word একাধিকবার queue-তে ঢুকে কাজ ফুলে যায় (BFS-এ push-এই mark করো)।
  • end_word list-এ আছে কিনা শুরুতে check না করা — শেষে অপ্রয়োজনীয় কাজ।
  • BFS-এর বদলে DFS ব্যবহার করা — DFS সবচেয়ে ছোট path-এর গ্যারান্টি দেয় না।
  • sequence-এ word গুনতে গিয়ে off-by-one (begin-কেই 1 ধরা উচিত, edge সংখ্যা নয়)।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: BFS-এ unweighted shortest path (এই tracker-এর BFS গুচ্ছ; ../shortest-path.md-এর "queue → deque" row)। আটকে গেলে আগে সাধারণ grid-BFS (Rotting Oranges / Labyrinth) মনে করো — এখানে শুধু "grid cell"-এর জায়গায় "word", আর "পাশের cell"-এর জায়গায় "এক অক্ষর আলাদা word"। কাঠামো হুবহু এক।

পরের অনুশীলন

কৌশলটি মনে রাখুন

BFS on implicit graph: graph হাতে না পেলেও যদি "node কী, edge-এর নিয়ম কী" সংজ্ঞায়িত করা যায়, তবে সবচেয়ে ছোট transformation = BFS; neighbor on-the-fly বানাও (এখানে pattern-bucket দিয়ে দ্রুত)।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "Word Ladder = implicit graph-এ BFS; word = node, এক অক্ষর আলাদা = edge, neighbor খুঁজতে *-pattern bucket; deque দিয়ে layer ছড়াও, end pop = সবচেয়ে ছোট sequence।" 'সবচেয়ে কম ধাপে এক state থেকে আরেক state' দেখলেই implicit-graph BFS মনে পড়বে।

কোথায় কাজে লাগে

  • Spell-check / autocorrect suggestion path: এক বানান থেকে আরেকটায় এক-অক্ষর ধাপে পৌঁছানো — সবচেয়ে কম edit-এর শৃঙ্খল।
  • Genetic mutation distance: এক DNA/protein sequence থেকে আরেকটায় এক-অক্ষর mutation-এ পৌঁছানোর সবচেয়ে ছোট পথ (Minimum Genetic Mutation)।
  • Puzzle / state-space search: lock combination, slider puzzle, Rubik-ধাঁচ — প্রতিটা state = node, একটা move = edge, সবচেয়ে কম move খুঁজতে BFS।
  • Word games / ladder puzzles: "doublets" বা word-ladder ধাঁচের খেলায় সমাধান-পথ বের করা।
  • Network routing on implicit graph: যেখানে edge গুলো নিয়ম দিয়ে সংজ্ঞায়িত (পুরো graph store করা যায় না), সেখানে on-the-fly neighbor সহ shortest hop খোঁজা।

মূল pattern: graph হাতে না থাকলেও "node কী, edge-এর নিয়ম কী" সংজ্ঞায়িত করতে পারলে সবচেয়ে কম ধাপ = implicit-graph BFS।

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