Problem link ও উৎস
- **Original source:** Implicit graph-এ shortest-path-এর classic প্রয়োগ
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Hard
- **Pattern:** BFS on implicit graph (word = node, এক-অক্ষর-আলাদা = edge)
- **Basic idea inherited from:** BFS levels (এই tracker-এর BFS গুচ্ছ) + hashing ([../../05-hashing/](../../05-hashing/README.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা `begin_word`, একটা `end_word`, আর একগুচ্ছ word-এর list দেওয়া আছে। তুমি প্রতি ধাপে একটা word-এর ঠিক **একটা অক্ষর** বদলাতে পারো, কিন্তু শর্ত — বদলানোর পর যে নতুন word তৈরি হয়, সেটা list-এর মধ্যে থাকতে হবে। `begin_word` থেকে শুরু করে `end_word`-এ পৌঁছাতে সবচেয়ে ছোট transformation sequence-এ কয়টা word থাকে (begin আর end সহ), সেটা বের করো। পৌঁছানো না গেলে 0।
```text
begin = "hit", end = "cog"
list = hot, dot, dog, lot, log, cog
hit -> hot -> dot -> dog -> cog 5 টা word (সবচেয়ে ছোট)
উত্তর: 5
```
### Input ও output {#8-example-input-and-output}
```text
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
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো প্রতিটা word একটা শহর, আর দুটো শহরের মধ্যে সরাসরি রাস্তা আছে কেবল যদি তাদের নামে ঠিক একটা অক্ষর আলাদা হয়। তুমি `hit` শহর থেকে `cog` শহরে যেতে চাও, সবচেয়ে কম শহর ছুঁয়ে। তুমি তো সব রাস্তার ম্যাপ হাতে পাওনি — কিন্তু নিয়ম জানো (এক অক্ষর আলাদা)। তাই তুমি ঢেউয়ের মতো ছড়াও: এক ধাপে যত শহরে যাওয়া যায় সব ছোঁও, তারপর তাদের থেকে পরের ধাপ — যেদিন `cog` ছোঁবে, সেই ধাপ-সংখ্যাই সবচেয়ে ছোট পথ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে **BFS-এর "shortest path in unweighted graph"** ধারণার উপর (এই tracker-এর BFS গুচ্ছ, যেমন Rotting Oranges/Labyrinth)। মূল মোচড়: এখানে graph টা তোমাকে কেউ দেয়নি — তুমি নিজে বানাবে মাথায়। প্রতিটা word একটা node, আর দুটো word-এর মধ্যে edge আছে যদি তারা ঠিক একটা অক্ষরে আলাদা হয়। সব edge-এর "ওজন" সমান (এক ধাপ), তাই BFS-ই সবচেয়ে ছোট sequence দেয়। সাথে [../../05-hashing/](../../05-hashing/README.md)-এর set/dict লাগে দ্রুত lookup-এর জন্য।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো 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 করা থাকে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
তিনটা জিনিস: (১) একটা **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।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
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।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: explicit graph বানাও — প্রতি জোড়া word তুলনা করে দেখো তারা এক অক্ষরে আলাদা কিনা, হলে edge যোগ করো। তারপর সেই graph-এ সাধারণ BFS চালিয়ে `begin` থেকে `end`-এর দূরত্ব বের করো।
```text
1) প্রতি জোড়া (wi, wj)-এর জন্য: এক অক্ষর আলাদা হলে edge
2) তৈরি graph-এ BFS begin থেকে
3) end-এর level = উত্তর
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
সব জোড়া তুলনা করতে `O(N^2)` জোড়া, আর প্রতি জোড়ায় অক্ষর মেলাতে `O(L)` — মোট `O(N^2 · L)`, যেখানে N = word সংখ্যা, L = word দৈর্ঘ্য। N বড় হলে এটা ভয়ংকর ধীর। আসল অপচয়: আমরা প্রতিটা সম্ভাব্য জোড়া যাচাই করছি, অথচ neighbor আসলে অল্প — pattern-bucket দিয়ে সরাসরি "এক অক্ষর বদলালে কে হয়" বের করা যায়, সব জোড়া দেখা লাগে না।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: graph explicit-ভাবে বানানোই দরকার নেই। দুটো word neighbor কিনা সেটা একটা নিয়ম — আর নিয়মটা bucket দিয়ে দ্রুত প্রয়োগ করা যায়: একই `*`-pattern মেলানো সব word পরস্পরের neighbor। তাই BFS চলাকালীন on-the-fly neighbor বের করা সম্ভব, পুরো `O(N^2)` adjacency matrix ছাড়াই।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
আগে একবার ঘুরে প্রতিটা 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 ছড়ায়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "graph তো দেওয়া নেই" দেখে থেমো না — জিজ্ঞেস করো "node কী, আর edge-এর নিয়ম কী?" এখানে node = word, edge = এক-অক্ষর-আলাদা। graph-টা মাথায় বানিয়ে নিলেই Hard problem-টা চেনা BFS-এ মিলিয়ে যায়। ([../shortest-path.md](../shortest-path.md)-এর শেষ row: unweighted → plain BFS, deque।)
### ছবিতে বোঝা {#7-visual-explanation}
`begin="hit"` থেকে BFS-এর layer, `(word, steps)`:
```text
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-এ ধাপে ধাপে {#14-step-by-step-dry-run}
ছোট 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`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `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 মিলিয়ে দেখা {#17-output-walkthrough}
`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 {#25-javascript-solution-with-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 {#26-typescript-solution-with-test-cases}
```typescript
function wordLadder(beginWord: string, endWord: string, wordList: string[]): number {
const words: Set