Skip to content

022 — Word Ladder

Source

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

1. Problem in simple words

তোমাকে দেওয়া আছে একটা 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

2. Which basic idea does this inherit from?

এই 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।

3. What is the hidden math or logic?

লুকানো 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)।

4. Which data structure is needed?

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

5. Why this data structure fits

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-ই খাপ খায়।

6. Real-life analogy

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

7. Visual explanation

beginWord = hit, endWord = cog
patterns:  *ot -> {hot,dot,lot}   h*t -> {hit,hot}   ...

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 = উত্তর

8. Example input and 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

9. Brute force thinking

প্রথম সরল চিন্তা: 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 দিয়ে

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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

13. Thinking tweak

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

14. Step-by-step dry run

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

15. Python solution

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!")

16. Line-by-line code explanation

  • 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 নিঃশেষ তবু না পেলে অসম্ভব।

17. Output walkthrough

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

  • 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 দিয়ে এড়াও।

21. Which basic problem this inherits from

ভিত্তি: 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-এ পরিণত হয়।

22. Similar harder problems

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: "এক-চালে-এক-বদল করে গন্তব্যে সবচেয়ে কম ধাপ" শুনলেই 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।