কনটেন্টে যান

023 — Word Search II

Problem link ও উৎস

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

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

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

একটা অক্ষরের 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"]

Input ও 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"] -> []

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

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

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

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

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

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

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

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

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

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

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-এ পেলেও একবারই রাখে।

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

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

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

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

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

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

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

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

আগে সব 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।

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

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

ছবিতে বোঝা

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 নেই)।

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

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"]।

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

Python

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

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

  • 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 থেকে শুরুর সম্ভাব্য সূচনা-বিন্দু।

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

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

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

সময়

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

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

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

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

  • প্রতি 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।

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

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

ভিত্তি: 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-এ ফেরে।

পরের অনুশীলন

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

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

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

ভবিষ্যতের আমাকে: "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।