Problem link ও উৎস
- **Original source:** Classic grid backtracking exercise (find many words in a board via a trie)
- **Platform:** LeetCode —
- **Topic:** recursion / backtracking (backtracking + trie preview)
- **Difficulty:** Hard
- **Pattern:** backtracking + trie — সব word একটা trie-তে রেখে grid-এ একবার DFS
- **Basic idea inherited from:** Word Search; trie আসবে পরের এক section-এ
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা অক্ষরের grid (`board`) আর একগুচ্ছ `words` দেওয়া আছে। তোমার কাজ: এই word-গুলোর মধ্যে **কোনগুলো grid-এ পাওয়া যায়** তা বের করা — Word Search-এর সেই নিয়মেই (পাশাপাশি cell, একই cell এক word-এ একবার)। পার্থক্য: একটা word নয়, **অনেক** word একসাথে খুঁজতে হবে।
```text
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 {#8-example-input-and-output}
```text
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"] -> []
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা শব্দের তালিকা মুখস্থ রাখার বদলে তুমি একটা "শব্দ-গাছ" আঁকলে: একই শুরুর অক্ষরের শব্দগুলো একই ডাল ভাগ করে। এখন grid-এ আঙুল চালানোর সময় তুমি গাছের ওই ডাল ধরেই নামো — অক্ষর মিললে ডালে এগোও, না মিললে থামো (ওই দিকে কোনো শব্দ নেই)। একবার হেঁটেই সব শব্দ ধরা পড়ে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এ পেলেও একবারই রাখে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা word-এর জন্য আলাদাভাবে Word Search (#17) চালাও — `exist(board, word)` `True` দিলে word-টা রাখো।
```text
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 একসাথে এগোয়।
### ছবিতে বোঝা {#7-visual-explanation}
trie-তে নামি ও grid-এ DFS — সমান্তরাল। `words=["oath","oat"]` → trie; grid-path `o→a→t→h`:
```text
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-এ ধাপে ধাপে {#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"]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#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 থেকে শুরুর সম্ভাব্য সূচনা-বিন্দু।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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`।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Word Search (#17)-এর grid backtracking + in-place visited mark, এখানে trie দিয়ে বহু-word একসাথে। [../patterns.md](../patterns.md)-এর grid-backtracking pattern; trie-র পূর্ণ আলোচনা পরের এক section-এ আসবে (এখানে preview হিসেবে nested-dict রূপ)। search-target-গুলো নিজে index করার এই idea অনেক multi-pattern matching problem-এ ফেরে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Word Search (একটা word) —