022 — Word Ladder

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

Problem link ও উৎস

• Original source: Classic shortest-transformation interview problem
• Platform: LeetCode — https://leetcode.com/problems/word-ladder/
• Topic: graphs + hashing + strings
• Difficulty: Hard
• Pattern: Implicit graph + BFS + bucketing
• Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 09 graphs (shortest path on unweighted graph = BFS), 05 hashing (word set আর pattern bucket-এ O(1) lookup), আর 02 strings (এক-অক্ষর বদলের neighbor তৈরি)। তিনটা জোড়া লাগলেই efficient word ladder।

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

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

তোমাকে দেওয়া আছে একটা beginWord, একটা endWord, আর একটা শব্দের তালিকা (wordList)। প্রতিবার তুমি শব্দের ঠিক একটা অক্ষর বদলাতে পারো, কিন্তু বদলানোর পর শব্দটা তালিকায় থাকতে হবে। beginWord থেকে endWord-এ পৌঁছাতে সবচেয়ে ছোট chain-এ মোট কতগুলো শব্দ লাগে সেটা return করো (begin আর end সহ গুনে)। পৌঁছানো না গেলে 0।

উদাহরণ

beginWord = "hit", endWord = "cog"
wordList  = ["hot","dot","dog","lot","log","cog"]
chain : hit -> hot -> dot -> dog -> cog   (5টা শব্দ)
উত্তর : 5

Input ও output

উদাহরণ

Input : begin="hit", end="cog", words=["hot","dot","dog","lot","log","cog"]
Output: 5                       # hit->hot->dot->dog->cog

Edge case 1 (endWord তালিকায় নেই): begin="hit", end="cog", words=["hot","dot","dog"] -> 0
Edge case 2 (begin==প্রায় end): begin="a", end="c", words=["a","b","c"] -> 2   # a->c

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

ভাবো একটা শব্দ-খেলা: তুমি একটা শব্দ থেকে আরেকটায় যাবে, প্রতি চালে ঠিক একটা অক্ষর বদলে — কিন্তু প্রতিটা মাঝের শব্দ অভিধানে থাকতেই হবে। সবচেয়ে কম চালে গন্তব্যে পৌঁছানোই লক্ষ্য। BFS মানে তুমি একসাথে "এক চালে পৌঁছানো সব শব্দ", তারপর "দুই চালে পৌঁছানো সব", এভাবে রিং রিং করে ছড়াও — গন্তব্য যে রিং-এ প্রথম আসে সেটাই সবচেয়ে কম চাল।

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

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

এই problem তিনটা আগের chapter-এর tool জোড়া দেয়:

• 09 graphs (../../09-graphs/) থেকে: প্রতিটা শব্দ একটা node; এক-অক্ষর বদলে যাওয়া দুই শব্দের মধ্যে একটা edge; unweighted shortest path = BFS।
• 05 hashing (../../05-hashing/) থেকে: wordList-টা একটা set বানাই (O(1) membership), আর pattern→words bucket map বানাই দ্রুত neighbor খোঁজার জন্য।
• 02 strings (../../02-arrays-and-strings/) থেকে: প্রতিটা position-এ অক্ষর বদলে pattern (h*t) তৈরি, যা neighbor-দের জুড়ে দেয়।

একা BFS দেয় shortest-path frame; একা hashing দেয় fast lookup; string-trick neighbor বানায়। তিন মিলে efficient।

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

লুকানো logic: graph-টা explicit না, implicit — edge গুনে বানানো নেই, "এক অক্ষর আলাদা" rule থেকে on-the-fly বের হয়। আর যেহেতু প্রতিটা edge-এর weight সমান (1 step), BFS-এর প্রথম যে layer-এ endWord ধরা পড়ে, সেটাই shortest — কারণ BFS layer-by-layer দূরত্ব অনুযায়ী expand করে।

bucketing-এর গণিত: দুটো শব্দ neighbor if and only if তারা কোনো এক position-এ * বসালে একই pattern দেয়। তাই প্রতিটা pattern-এর নিচে সব মিলে-যাওয়া শব্দ জড়ো করলে neighbor খোঁজা প্রতিবার alphabet-scan না করে O(L) (L = শব্দের length)।

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

দরকার: (a) একটা queue BFS-এর জন্য (09 graphs), (b) একটা set/dict — pattern (h*t) থেকে সেই pattern-এর শব্দগুলোর list (05 hashing), আর (c) একটা visited set যাতে একই শব্দ দুবার expand না হয়। শব্দ-manipulation-এ string slicing (02)।

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

queue (09) দেয় BFS-এর layered order — তাই প্রথম hit-ই shortest। pattern→words dict (05) neighbor খোঁজাকে O(L) করে: প্রতি position-এ * বসিয়ে সেই bucket-এর সব শব্দ সরাসরি পাও, পুরো wordList scan করা লাগে না (যা O(N·L) হত প্রতি node-এ)। visited set duplicate expansion ঠেকায়, নাহলে cycle-এ আটকে যেত। array/list দিয়ে membership চেক O(N) হত — তাই hashing-ই খাপ খায়।

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

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

প্রথম সরল চিন্তা: BFS করি, কিন্তু কোনো শব্দের neighbor খুঁজতে wordList-এর প্রতিটা শব্দের সাথে তুলনা করি — কয়টা অক্ষরে আলাদা গুনে, ঠিক 1 হলে neighbor।

উদাহরণ

neighbors(word):
    result = []
    for w in wordList:
        if differ_by_one(word, w):   # L অক্ষর তুলনা
            result.append(w)
    return result
# তারপর সাধারণ BFS এই neighbors দিয়ে

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

প্রতিটা শব্দের neighbor খুঁজতে পুরো wordList scan + প্রতিটায় L-অক্ষর তুলনা = O(N·L) প্রতি node, আর N node মিলে O(N²·L)। N বড় হলে ধীর। কারণ একই "এক-অক্ষর-আলাদা" সম্পর্ক বারবার নতুন করে গুনছি — bucketing (05 hashing) এটা precompute করে O(L)-এ নামায়।

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

মূল observation: neighbor-সম্পর্ককে আগেই index করে ফেলা যায়। প্রতিটা শব্দের প্রতি position-এ * বসালে একটা generic pattern পাও; একই pattern-ওয়ালা সব শব্দ পরস্পরের neighbor। তাই pattern→words bucket একবার বানিয়ে নিলে, যেকোনো শব্দের neighbor = তার L-টা pattern-এর bucket একত্র করা — scan লাগে না।

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

আগে pattern→words dict বানাও: প্রতিটা শব্দের প্রতি position-এ * বসিয়ে সেই pattern-এর তালিকায় শব্দটা যোগ করো। তারপর begin থেকে BFS: queue থেকে শব্দ তোলো, তার L-টা pattern বের করো, প্রতিটা bucket-এর শব্দগুলো neighbor — unvisited হলে queue-তে দাও (depth +1)। endWord প্রথম যে depth-এ ধরা পড়ে সেটাই উত্তর; queue শেষ হলেও না পেলে 0।

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

মোচড়: "graph কোথায়, edge list তো নেই" ভাবা ছাড়ো। ভাবো "node হলো শব্দ, edge হলো এক-অক্ষর-বদল rule" — graph-টা rule থেকে on-the-fly জন্মায়। তখন এটা নিছক unweighted shortest path = BFS, আর hashing শুধু neighbor-খোঁজাকে fast করার tool।

ছবিতে বোঝা

উদাহরণ

beginWord = hit, endWord = cog
সব pattern bucket (beginWord-সহ):
*it:{hit}      h*t:{hit,hot}   hi*:{hit}
*ot:{hot,dot,lot}  ho*:{hot}  d*t:{dot}
do*:{dot,dog}  *og:{dog,log,cog}  d*g:{dog}
l*t:{lot}     lo*:{lot,log}  l*g:{log}
c*g:{cog}     co*:{cog}

BFS layers (দূরত্ব = chain length):
 layer 1:  hit                       (length 1)
 layer 2:  hot                       (length 2)   [hit-এর neighbor]
 layer 3:  dot, lot                  (length 3)
 layer 4:  dog, log                  (length 4)
 layer 5:  cog  <- পাওয়া গেল!        (length 5)

প্রথম যেই layer-এ cog এলো = 5 = উত্তর

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

begin="hit", end="cog", words=["hot","dot","dog","lot","log","cog"]:

1. buckets বানাও: *it:{hit}, h*t:{hit,hot}, ho*:{hot}, *ot:{hot,dot,lot}, d*t:{dot}, ... co*:{cog} ইত্যাদি
2. queue=[(hit,1)], visited={hit}
3. pop (hit,1): patterns *it,h*t,hi* → neighbor hot → queue=[(hot,2)], visited+={hot}
4. pop (hot,2): patterns দেয় dot,lot → queue=[(dot,3),(lot,3)]
5. pop (dot,3): dog → (dog,4); pop (lot,3): log → (log,4)
6. pop (dog,4): cog = endWord! → return 4+1 = 5

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

Python

Python

from collections import deque, defaultdict

def ladder_length(begin_word, end_word, word_list):
    words = set(word_list)                  # 05 hashing: O(1) membership
    if end_word not in words:
        return 0
    L = len(begin_word)

    buckets = defaultdict(list)             # pattern -> শব্দের list
    for w in words:                         # 02 strings: প্রতি position-এ *
        for i in range(L):
            buckets[w[:i] + "*" + w[i+1:]].append(w)

    queue = deque([(begin_word, 1)])        # 09 graphs: BFS layered
    visited = {begin_word}
    while queue:
        word, steps = queue.popleft()
        if word == end_word:
            return steps
        for i in range(L):                  # এই শব্দের L-টা pattern
            pat = word[:i] + "*" + word[i+1:]
            for nxt in buckets[pat]:        # bucket = ready neighbors
                if nxt not in visited:
                    visited.add(nxt)
                    queue.append((nxt, steps + 1))
            buckets[pat] = []               # bucket নিঃশেষ: পুনরায় scan ঠেকাও
    return 0

# ---- tests ----
assert ladder_length("hit", "cog", ["hot","dot","dog","lot","log","cog"]) == 5
assert ladder_length("hit", "cog", ["hot","dot","dog"]) == 0   # cog নেই
assert ladder_length("a", "c", ["a","b","c"]) == 2             # a->c
assert ladder_length("hot", "dog", ["hot","dog","dot"]) == 3   # hot->dot->dog
assert ladder_length("hit", "hit", ["hit"]) == 1              # ইতিমধ্যে গন্তব্য
print("সব test pass!")

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

• words = set(word_list) — list-কে set বানিয়ে O(1) membership (05 hashing)।
• if end_word not in words: return 0 — গন্তব্যই তালিকায় না থাকলে কখনো পৌঁছানো যাবে না।
• buckets লুপ — প্রতিটা শব্দের প্রতি position-এ * বসিয়ে pattern→words bucket গড়ে; neighbor-relation precompute (02 + 05)।
• queue = deque([(begin_word, 1)]) — BFS শুরু, step count 1 (begin নিজেও chain-এ গোনা)।
• if word == end_word: return steps — BFS-এর প্রথম hit = shortest (09 graphs)।
• inner for i / for nxt — current শব্দের L-টা pattern-এর bucket থেকে unvisited neighbor queue-তে, depth+1।
• buckets[pat] = [] — একটা bucket একবার ব্যবহার হলে খালি করি, যাতে পরে আবার scan না হয় (efficiency)।
• return 0 — queue নিঃশেষ তবু না পেলে অসম্ভব।

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

hit→cog example-এ BFS layer 1..5 ঘুরে layer 5-এ cog ধরা পড়ে → 5; assert pass। cog না থাকলে শুরুতেই 0। a→c এ a→c এক ধাপে → 2। begin==end হলে প্রথম pop-এই match → 1। সব assert pass; শেষে print: সব test pass!।

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

সময়

O(N · L²) — N শব্দ, প্রতিটার L position-এ * বসিয়ে pattern বানানো প্রতিটা O(L) (slicing), মোট bucket-গড়া O(N·L²); BFS-এ প্রতিটা শব্দ ও pattern একবারই process হয়। (L = শব্দের length, N = শব্দসংখ্যা।)

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

O(N · L²) — buckets-এ N·L pattern, প্রতিটা key O(L) দীর্ঘ; queue/visited বড়জোর O(N)।

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

• BFS-এর বদলে DFS ব্যবহার করা — DFS shortest দেয় না; unweighted shortest path-এ BFS লাগবেই।
• visited চিহ্ন না রাখা (বা pop-এর সময় রাখা) — তখন একই শব্দ বারবার queue-তে ঢুকে cycle/TLE হয়; enqueue-এর সময়ই visited mark করো।
• endWord তালিকায় আছে কি না আগে চেক না করা — অযথা পুরো BFS চালানো।
• প্রতিবার পুরো wordList scan করে neighbor খোঁজা (brute) — O(N²·L); bucketing দিয়ে এড়াও।

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

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

ভিত্তি: unweighted graph-এ BFS shortest path (09 graphs-এর ../../09-graphs/) + set/dict দিয়ে O(1) lookup আর bucketing (05 hashing-এর ../../05-hashing/) + string slicing দিয়ে neighbor গঠন (02-এর ../../02-arrays-and-strings/)। এই তিনটা জানা থাকলে word ladder একটা চেনা BFS-এ পরিণত হয়।

পরের অনুশীলন

• Word Ladder II (শুধু length না, সব shortest path গুলো ফেরত — BFS + parent backtrack) — https://leetcode.com/problems/word-ladder-ii/
• Open the Lock (একই implicit-graph BFS, digit ঘোরানো) — https://leetcode.com/problems/open-the-lock/
• Minimum Genetic Mutation (অক্ষরের বদলে gene char; হুবহু একই engine) — https://leetcode.com/problems/minimum-genetic-mutation/

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

Implicit graph + BFS + bucketing: যখন node-গুলো একটা rule-এ পরস্পর জুড়ে (এক-অক্ষর বদল), graph-টা না বানিয়ে rule থেকে neighbor জন্মাও, unweighted shortest path-এ BFS চালাও, আর hashing দিয়ে neighbor-খোঁজা fast করো। "shortest transformation/steps" problem-এর canonical রূপ।

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

ভবিষ্যতের আমাকে: "এক-চালে-এক-বদল করে গন্তব্যে সবচেয়ে কম ধাপ" শুনলেই implicit graph + BFS মনে করবে। প্রতিটা state একটা node, rule দেয় edge, BFS-এর প্রথম hit-ই shortest। neighbor scan ধীর হলে pattern bucket (h*t) দিয়ে hashing-এ precompute করো। visited enqueue-এর সময় mark করো। এটা graphs + hashing + strings-এর পরিষ্কার মেলবন্ধন।

---

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