Skip to content

023 — Word Search II

Source

  • Original source: Classic grid backtracking exercise (find many words in a board via a trie)
  • Platform: LeetCode — https://leetcode.com/problems/word-search-ii/
  • Topic: recursion / backtracking (backtracking + trie preview)
  • Difficulty: Hard
  • Pattern: backtracking + trie — সব word একটা trie-তে রেখে grid-এ একবার DFS
  • Basic idea inherited from: Word Search; trie আসবে পরের এক section-এ

1. Problem in simple words

একটা অক্ষরের grid (board) আর একগুচ্ছ words দেওয়া আছে। তোমার কাজ: এই word-গুলোর মধ্যে কোনগুলো grid-এ পাওয়া যায় তা বের করা — Word Search-এর সেই নিয়মেই (পাশাপাশি cell, একই cell এক word-এ একবার)। পার্থক্য: একটা word নয়, অনেক word একসাথে খুঁজতে হবে।

board = [[o, a, a, n],
         [e, t, a, e],
         [i, h, k, r],
         [i, f, l, v]]

words = ["oath", "pea", "eat", "rain"] -> পাওয়া যায়: ["eat", "oath"]

2. Which basic idea does this inherit from?

ভিত্তি হলো Word Search, এবার একসাথে অনেক word। সরল উপায় — প্রতিটা word-এর জন্য আলাদা করে Word Search চালানো; কিন্তু words বড় হলে এটা অপচয়, কারণ একই grid বারবার হাঁটা হয়। তাই আমরা সব word একটা trie (prefix tree)-তে রাখি, আর grid-এ একবার DFS করি — DFS-এর সাথে trie-তেও সমান্তরালে নামি। trie-র বিস্তারিত পরের এক section-এ; এখানে এটুকু জানলেই চলবে — trie হলো শব্দগুলোর common prefix ভাগ করে নেওয়া একটা গাছ।

3. What is the hidden math or logic?

লুকানো logic হলো prefix sharing: অনেক word-এর শুরুর অক্ষর একই হতে পারে ("eat", "eats", "ear" — সবার "ea")। trie এই common prefix একবারই রাখে, তাই grid-এ একটা path হাঁটার সময় একসাথে অনেক word-এর সম্ভাবনা যাচাই হয়। আরও গুরুত্বপূর্ণ — DFS-এর বর্তমান অক্ষর trie-র কোনো child না হলে ওই path-এ আর কোনো word সম্ভব নয়, তাই branch সঙ্গে সঙ্গে কাটা পড়ে (trie-driven pruning)।

4. Which data structure is needed?

লাগে একটা trie (nested dict — প্রতিটা node এক অক্ষর থেকে পরের node-এ map, শেষে word-marker); board (in-place visited mark সহ DFS-এর জন্য); একটা set found (পাওয়া word, duplicate এড়াতে); আর recursion-এর জন্য call stack।

5. Why this data structure fits

trie একসাথে সব word ধরে রাখে এবং common prefix ভাগ করে, তাই grid-এর একটা path-এ নেমে একসাথে অনেক word-এর সাথে মিল যাচাই হয় — প্রতি word-এ আলাদা DFS-এর O(words × m × n × 4^L) খরচ এড়ায়। nested dict-এ child-lookup ও word-marker check O(1)। DFS-এ cell in-place # mark করায় visited-check O(1) ও extra memory নেই। found set একই word একাধিক path-এ পেলেও একবারই রাখে।

6. Real-life analogy

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

7. Visual explanation

trie-তে নামি ও grid-এ DFS — সমান্তরাল। words=["oath","oat"] → trie; grid-path o→a→t→h:

trie:  root -(o)- o -(a)- a -(t)- t -(h)- h[word:"oath"]
                                  └ [word:"oat"]

grid DFS, node সমান্তরাল:
  go(0,0,'o'->root.o) -> go(0,1,'a'->.a) -> go(1,1,'t'->.t)  [".t"-এ "oat" marker -> found]
       -> go(2,1,'h'->.h)  [".h"-এ "oath" marker -> found]

board[r][c] trie-node-এ child না হলে -> থামো (ওই path-এ word নেই)।

8. Example input and output

board = [[o,a,a,n],[e,t,a,e],[i,h,k,r],[i,f,l,v]]
Input : words=["oath","pea","eat","rain"] -> Output: ["eat", "oath"]

Edge case 1 (cell পুনর্ব্যবহার লাগে): board=[[a,b],[c,d]], words=["abcb"] -> []
Edge case 2 (এক cell): board=[[a]], words=["a"] -> ["a"];  words=["b"] -> []

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা word-এর জন্য আলাদাভাবে Word Search (#17) চালাও — exist(board, word) True দিলে word-টা রাখো।

result = []
for word in words:
    if exist(board, word):     # প্রতিটা word-এ পুরো grid আবার DFS
        result.append(word)
return result

10. Why brute force is slow

প্রতিটা word-এর জন্য পুরো grid আলাদা করে হাঁটা হয় — words বড় হলে (যেমন হাজারখানেক) একই path বহুবার পুনরাবৃত্ত হয়, common prefix-এর কোনো সুবিধা নেওয়া হয় না। trie version সব word একসাথে রেখে grid-এ একবার DFS করে: একটা path হাঁটার সময় যত word-এর prefix মেলে সব একসাথে যাচাই হয়, আর কোনো prefix trie-তে না থাকলে branch সঙ্গে সঙ্গে কাটা — তাই বহু-word ক্ষেত্রে নাটকীয়ভাবে দ্রুত।

11. Key observation

মূল observation: word-গুলোর common prefix একবারই হাঁটা উচিত। প্রতি word-এ আলাদা DFS না করে সব word-কে একটা trie-তে রাখো, আর grid-DFS-এর সাথে trie-তেও নামো — বর্তমান cell trie-node-এ child না হলে ওই দিকে কোনো word সম্ভব নয়, থামো। মানে trie নিজেই pruning-এর গাইড।

12. Optimized intuition

আগে সব word একটা trie-তে ঢোকাও (শেষ node-এ পুরো word marker)। grid-এর প্রতিটা cell থেকে go(r, c, node): nxt = node.get(board[r][c]); None হলে (অক্ষর trie-child নয়, বা #) return; nxt-এ word-marker থাকলে found-এ যোগ; cell mark (#), 4 দিকে go(.., nxt), ফিরে restore। শেষে sorted(found)। DFS + trie-walk সমান্তরাল, একবারেই সব word।

13. Thinking tweak

মোচড়: "প্রতিটা word আলাদা করে খুঁজব" নয় — সব word-কে একটা গাছে জড়ো করে grid-এ একবারই হাঁটো। search-target-গুলোকে নিজেদের মধ্যে index (trie) করে নিলে অনেক query একসাথে চলে। Word Search-এ word ছিল গাইড; এখানে trie গাইড — অক্ষরে অক্ষরে DFS আর trie একসাথে এগোয়।

14. Step-by-step dry run

find_words(board, ["oath","eat"]), go(r, c, node):

  1. trie গড়া: root→o→a→t→h["oath"], root→e→a→t["eat"]।
  2. বাইরের loop cell (0,0)='o': go(0,0,root) → nxt=root['o']; mark; প্রতিবেশীতে নামো।
  3. (0,1)='a': nxt=...['a']; পরে (1,1)='t', তারপর (2,1)='h': marker "oath" → found={"oath"}।
  4. cell (1,3)='e' থেকে: e→a((1,2))→t((1,1)): marker "eat" → found={"oath","eat"}।
  5. return sorted(found) = ["eat", "oath"]।

15. Python solution

def find_words(board, words):
    # ---- trie গড়া (nested dict; "$" = এই node-এ পুরো word শেষ) ----
    trie = {}
    for w in words:
        node = trie
        for ch in w:
            node = node.setdefault(ch, {})
        node["$"] = w

    rows, cols = len(board), len(board[0])
    found = set()

    def go(r, c, node):
        nxt = node.get(board[r][c])      # '#' বা অমিল অক্ষর -> None
        if nxt is None:
            return
        if "$" in nxt:                   # পুরো word শেষ -> পাওয়া গেল
            found.add(nxt["$"])
        ch = board[r][c]
        board[r][c] = "#"                # CHOOSE: visited mark
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                go(nr, nc, nxt)          # EXPLORE: trie-তেও nxt-এ নামি
        board[r][c] = ch                 # UN-CHOOSE: mark সরাও

    for r in range(rows):
        for c in range(cols):
            go(r, c, trie)               # প্রতি cell থেকে trie-root ধরে শুরু
    return sorted(found)

# ---- tests ----
board = [["o", "a", "a", "n"],
         ["e", "t", "a", "e"],
         ["i", "h", "k", "r"],
         ["i", "f", "l", "v"]]
assert find_words([row[:] for row in board], ["oath", "pea", "eat", "rain"]) == ["eat", "oath"]
assert find_words([["a", "b"], ["c", "d"]], ["abcb"]) == []   # cell পুনর্ব্যবহার লাগত
assert find_words([["a"]], ["a"]) == ["a"]
assert find_words([["a"]], ["b"]) == []
assert find_words([["a", "b"], ["c", "d"]], ["ab", "ac", "bd", "abdc"]) == ["ab", "abdc", "ac", "bd"]
print("সব test pass!")

16. Line-by-line code explanation

  • node.setdefault(ch, {}) — trie-তে ch-এর child না থাকলে খালি dict বানিয়ে নামো; word-গড়া।
  • node["$"] = w — শেষ node-এ পুরো word marker (cut-off $ অক্ষরে নেই, তাই নিরাপদ key)।
  • nxt = node.get(board[r][c]) — বর্তমান অক্ষর trie-child কিনা; '#' বা অমিল হলে None।
  • if nxt is None: return — গেট: ওই path-এ আর কোনো word সম্ভব নয়।
  • if "$" in nxt: found.add(nxt["$"]) — এই cell-এ এসে একটা word সম্পূর্ণ হলে জমাও।
  • board[r][c] = "#" ... board[r][c] = ch — CHOOSE/UN-CHOOSE: in-place visited mark ও restore।
  • go(nr, nc, nxt) — EXPLORE: grid-এ প্রতিবেশীতে, trie-তে nxt-এ — সমান্তরাল।
  • বাইরের loop — প্রতিটা cell trie-root থেকে শুরুর সম্ভাব্য সূচনা-বিন্দু।

17. Output walkthrough

find_words: সব word trie-তে গেঁথে নিয়ে প্রতিটা cell থেকে একবার DFS — grid ও trie একসাথে নামে। "oath" ও "eat"-এর জন্য বৈধ path আছে, তাই found-এ ওঠে; "pea"/"rain"-এর শুরুর অক্ষরই grid-path-এ trie-child হয় না, তাই দ্রুত বাদ। nxt is None গেট '#'-marked cell ও trie-বহির্ভূত অক্ষর দুটোই সামলায়, তাই আলাদা visited-check লাগে না। ফল sorted(found) দিয়ে স্থিতিশীল ক্রমে। সব মিলে print: সব test pass!।

18. Time complexity

worst case O(m · n · 4^L) — m·nটা start cell, প্রতি path-এ গভীরতা L (সবচেয়ে লম্বা word), প্রতি step-এ ≤ 4 দিক (প্রথম পরে ≤ 3)। trie-driven pruning বাস্তবে বেশিরভাগ branch তাড়াতাড়ি কাটে। trie গড়তে O(সব word-এর মোট অক্ষর)।

19. Space complexity

O(সব word-এর মোট অক্ষর) trie-র জন্য, প্লাস DFS-এর call stack O(L)। board in-place mark করায় আলাদা visited-structure লাগে না। found set সর্বোচ্চ word-সংখ্যা পর্যন্ত।

20. Common mistakes

  • প্রতি word-এ আলাদা DFS চালানো (trie না বানানো) — বহু-word-এ ধীর; common prefix-এর সুবিধা হারায়।
  • word-marker key হিসেবে এমন অক্ষর নেওয়া যা word-এ থাকতে পারে — "$" (বা bool flag) নাও, যা কখনো child-অক্ষরের সাথে সংঘর্ষ করবে না।
  • backtrack-এ board[r][c] = ch restore ভুলে যাওয়া — cell চিরতরে #, পরের word আটকে যায়।
  • duplicate word একাধিক path-এ পেলে list-এ দুবার ঢোকা — set ব্যবহার করো, শেষে sorted।

21. Which basic problem this inherits from

ভিত্তি: Word Search (#17)-এর grid backtracking + in-place visited mark, এখানে trie দিয়ে বহু-word একসাথে। ../patterns.md-এর grid-backtracking pattern; trie-র পূর্ণ আলোচনা পরের এক section-এ আসবে (এখানে preview হিসেবে nested-dict রূপ)। search-target-গুলো নিজে index করার এই idea অনেক multi-pattern matching problem-এ ফেরে।

22. Similar harder problems

23. Pattern learned

Backtracking + trie (multi-pattern grid search): অনেক search-target থাকলে সেগুলো একটা trie-তে index করো, তারপর grid-এ একবার DFS করে DFS ও trie সমান্তরালে নামাও; cell trie-child না হলে branch বাদ — common prefix ভাগ করে একসাথে বহু word খোঁজার কঙ্কাল।

24. Final summary

ভবিষ্যতের আমাকে: "Word Search II = সব word trie-তে রাখো; প্রতি cell থেকে go(r,c,node) — grid ও trie একসাথে নামো; node-এ '$' থাকলে word found; cell mark/restore।" যখনই 'একটা grid/text-এ অনেক pattern একসাথে খোঁজো' শুনবে — এই trie + backtracking skeleton মনে করবে; target-গুলো আগে index করো।

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