Problem link ও উৎস
- **Original source:** Classic grid backtracking exercise (path-spelling a word)
- **Platform:** LeetCode —
- **Topic:** recursion / backtracking (grid backtracking, visited marks)
- **Difficulty:** Medium
- **Pattern:** grid backtracking — প্রতি cell থেকে 4 দিকে DFS, visited cell mark করে চলো
- **Basic idea inherited from:** Constraint backtracking + cell-এ seen-set
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা অক্ষরের grid (`board`) আর একটা `word` দেওয়া আছে। তোমার কাজ: grid-এর ভেতরে এমন একটা path আছে কিনা বলা, যেটা ধরে হাঁটলে `word`-এর অক্ষরগুলো পরপর মেলে। নিয়ম দুটো — পরপর অক্ষর অবশ্যই **পাশাপাশি cell** (উপর/নিচ/বাঁ/ডান, কোনাকুনি নয়) থেকে নিতে হবে, আর **একই cell একবারের বেশি ব্যবহার করা যাবে না**। থাকলে `True`, নাহলে `False`।
```text
board = [[A, B, C, E],
[S, F, C, S],
[A, D, E, E]]
word = "ABCCED" -> True (A→B→C→C→E→D একটানা পাশাপাশি path)
word = "ABCB" -> False (দ্বিতীয় B-র জন্য cell পুনর্ব্যবহার লাগত, নিষেধ)
```
### Input ও output {#8-example-input-and-output}
```text
board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]]
Input : word="ABCCED" -> Output: True
Input : word="SEE" -> Output: True
Input : word="ABCB" -> Output: False (cell পুনর্ব্যবহার লাগত)
Edge case 1 (এক cell): board=[[A]], word="A" -> True
Edge case 2 (নেই): board=[[A]], word="B" -> False
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
word-search puzzle বা Boggle-এর কথা ভাবো: আঙুল দিয়ে অক্ষর ছুঁয়ে ছুঁয়ে একটা শব্দ ট্রেস করছ। নিয়ম — পাশাপাশি ঘরে যেতে হবে, আর একই ঘর এই শব্দের জন্য দুবার ছোঁয়া যাবে না। ভুল দিকে গেলে আঙুল পিছিয়ে এনে অন্য দিক চেষ্টা করো — সেটাই backtracking, আর "ছুঁয়েছি" চিহ্নটা তুলে ফেলাই un-choose।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো **constraint backtracking + প্রতি cell-এ একটা seen-set**। Generate Parentheses-এ প্রতি step-এ একটা validity গেট ছিল; এখানে গেট দুটো — (a) cell-এর অক্ষর `word`-এর প্রত্যাশিত অক্ষরের সাথে মেলে কিনা, (b) cell-টা এই path-এ আগে ব্যবহার হয়েছে কিনা। "seen" আলাদা set-এ না রেখে আমরা cell-টাকেই সাময়িক একটা placeholder (`#`) দিয়ে mark করি, ফিরে এসে restore করি — choose/un-choose-এর grid রূপ।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **grid আসলে একটা implicit graph**: প্রতিটা cell একটা node, প্রতিটা cell-এর edge তার 4টা প্রতিবেশীর দিকে। আমরা খুঁজছি এমন একটা **simple path** (কোনো node দুবার নয়) যার অক্ষর-ক্রম ঠিক `word`। এটা graph-এর DFS, কিন্তু path-constraint সহ (vertex পুনরাবৃত্তি নিষেধ)। প্রথম পদক্ষেপের পর প্রতিটা cell-এ branching ≤ 3, কারণ যে দিক থেকে এলাম সেটা mark করা — তাই গাছ 4-ary নয়, কার্যত 3-ary।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
`board` 2D list-টাই দ্বৈত ভূমিকা নেয় — grid আর visited-marker একসাথে। লাগে একটা **integer `i`** (`word`-এর কত অক্ষর মিলেছে), recursion-এর জন্য **call stack**, আর dimension জানতে `rows`/`cols`। চাইলে আলাদা `visited` set রাখা যায়, কিন্তু in-place `#` mark বেশি মেমরি-সাশ্রয়ী।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
cell-কে in-place `#` দিয়ে mark করলে "এই path-এ আগে এসেছি?" check ও restore দুটোই O(1) — আলাদা set-এর overhead নেই। call stack নিজেই বর্তমান path-টা ধরে রাখে, তাই আলাদা path-list লাগে না। আর backtrack-এ original অক্ষর ফিরিয়ে দিই বলে পরের start-cell থেকে DFS শুরু করার সময় board আবার পরিষ্কার — কোনো leak নেই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা cell-কে শুরু ধরে, প্রতি step-এ চারদিকেই অন্ধভাবে যাও — `len(word)` দৈর্ঘ্যের সব সম্ভাব্য path গড়ো, তারপর প্রতিটা path-এর অক্ষর `word`-এর সাথে মিলিয়ে দেখো।
```text
for each start cell (r, c):
for each path of length len(word) walking 4 directions:
if path spells word and uses no cell twice:
return True
return False
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
অক্ষর-মিল না দেখে অন্ধভাবে চারদিকে গেলে প্রতিটা start থেকে প্রায় `4^L` path (`L = len(word)`) গড়তে হয়, তারপর শেষে মিলিয়ে দেখা — বিপুল অপচয়। backtracking প্রতিটা step-এই অক্ষর মিলিয়ে নেয়: যে cell-এর অক্ষর `word[i]`-এর সাথে মেলে না, সেই branch সঙ্গে সঙ্গে কাটা পড়ে (pruning)। তাছাড়া উত্তর শুধু "আছে কি নেই" — তাই প্রথম path পেলেই short-circuit করে `True` ফেরাই, বাকি কিছু explore করি না।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **একটাই path লাগবে, পেলেই থামো**, আর প্রতিটা step-এ একটা অক্ষর-মিলের গেট path-গাছকে বিপুল ছাঁটে। "পুরো word grid-এ আছে?" না ভেবে ভাবো "আমি `word[i]`-তে দাঁড়িয়ে; কোন প্রতিবেশী `word[i+1]` বহন করতে পারে?" — locally একটা ছোট মিল, recursion বাকি path বের করে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`go(r, c, i)`: base case `i == len(word)` → সব অক্ষর মিলেছে, `True`। bounds-এর বাইরে বা `board[r][c] != word[i]` → `False`। নাহলে cell mark করো (`#`), 4 দিকে `go(.., i+1)` — যেকোনোটা `True` হলে চেইন `True`; শেষে cell restore (un-choose)। বাইরের loop প্রতিটা cell-কে শুরু হিসেবে চেষ্টা করে।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** grid-এর "visited" রাখতে আলাদা data structure লাগে না — cell-টাকেই সাময়িক বদলে দাও, ফিরে এসে আগের অক্ষর বসিয়ে দাও। state আর board আলাদা না রেখে একটাই board-এ choose/un-choose করলে কোড ছোট আর মেমরি কম। বড় "word আছে কিনা" প্রশ্নটা নেমে আসে "এই cell + পরের অক্ষর"-এ।
### ছবিতে বোঝা {#7-visual-explanation}
`go(r, c, i)`: bounds/mismatch হলে False; অক্ষর মিললে mark করে 4 দিকে recurse, ফিরে unmark। `word="AB"`, `board=[[A,B],[C,D]]`-এ `go(0,0,0)`:
```text
go(0,0, i=0) board[0][0]='A'==word[0] ✓ -> mark '#'
↓(1,0) ↑(-1,0) →(0,1) ←(0,-1)
go(1,0,1) bound বাইরে go(0,1,1) bound বাইরে
'C'!=word[1] False 'B'==word[1] ✓ False
False go(.., i=2): i==len -> True
\-> পুরো call True
i == len(word) -> পুরো word মিলেছে; কোনো branch True হলেই থামো।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`exist([[A,B],[C,D]], "ABD")`, `go(r, c, i)`:
1. বাইরের loop `go(0,0,0)`: `'A'==word[0]` ✓; mark `(0,0)='#'`।
2. `(0,0)` থেকে নিচে `go(1,0,1)`: `'C'!=word[1]('B')` → False।
3. `(0,0)` থেকে ডানে `go(0,1,1)`: `'B'==word[1]` ✓; mark `(0,1)='#'`।
4. `(0,1)` থেকে নিচে `go(1,1,2)`: `'D'==word[2]` ✓; mark; নিচের call `go(.., i=3)`: `i==len` → `True`।
5. চেইন `True` ফিরে আসে; cell-গুলো restore হয়; `exist` → `True`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def exist(board, word):
if not board or not board[0]:
return False
rows, cols = len(board), len(board[0])
def go(r, c, i):
if i == len(word): # base case: সব অক্ষর মিলেছে
return True
if (r < 0 or r >= rows or c < 0 or c >= cols
or board[r][c] != word[i]): # bounds বা mismatch গেট
return False
tmp = board[r][c]
board[r][c] = "#" # CHOOSE: visited mark
found = (go(r + 1, c, i + 1) or
go(r - 1, c, i + 1) or
go(r, c + 1, i + 1) or
go(r, c - 1, i + 1)) # 4 দিকে EXPLORE
board[r][c] = tmp # UN-CHOOSE: mark সরাও
return found
for r in range(rows):
for c in range(cols):
if go(r, c, 0): # প্রতিটা cell-কে শুরু ধরে চেষ্টা
return True
return False
# ---- tests (board-এর copy পাঠাই, যেন একটা test অন্যটাকে নষ্ট না করে) ----
b1 = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
assert exist([row[:] for row in b1], "ABCCED") is True
assert exist([row[:] for row in b1], "SEE") is True
assert exist([row[:] for row in b1], "ABCB") is False # cell পুনর্ব্যবহার নিষেধ
assert exist([["A"]], "A") is True
assert exist([["A"]], "B") is False
assert exist([["A", "B"], ["C", "D"]], "ACDB") is True # A→C→D→B বাঁক
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if i == len(word): return True` — base case: সব অক্ষর মিলে গেছে, path পাওয়া গেছে।
- `if r<0 ... or board[r][c] != word[i]: return False` — bounds পেরোলে বা অক্ষর না মিললে এই branch বাদ (গেট)।
- `tmp = board[r][c]; board[r][c] = "#"` — CHOOSE: cell-টা সাময়িক mark, যেন এই path-এ আর না ব্যবহার হয়।
- `go(r±1/c±1, .., i+1)` — চারদিকে EXPLORE, পরের অক্ষরের খোঁজে; `or` বলে যেকোনোটা True হলেই থামে।
- `board[r][c] = tmp` — UN-CHOOSE: mark সরিয়ে আসল অক্ষর ফেরত, যাতে অন্য path এই cell ফের ব্যবহার করতে পারে।
- বাইরের double loop — যেহেতু word grid-এর যেকোনো cell থেকে শুরু হতে পারে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`exist`-এ চারটা মূল পরীক্ষা: `"ABCCED"` ও `"SEE"`-এর জন্য বৈধ পাশাপাশি path আছে → `True`; `"ABCB"`-তে দ্বিতীয় `B`-র জন্য একটা cell দুবার লাগত, কিন্তু mark করা থাকায় `board[r][c] != word[i]` গেটে আটকে যায় → `False`। এক-cell board-এ মিল/অমিল দেখায় edge। `"ACDB"` দেখায় path বাঁক নিতে পারে (A→C→D→B)। প্রতিটা assert-এ board-এর copy পাঠাই বলে state leak নেই। সব মিলে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function exist(board, word) {
if (!board.length || !board[0].length) return false;
const rows = board.length, cols = board[0].length;
const go = (r, c, i) => {
if (i === word.length) return true; // base case: সব অক্ষর মিলেছে
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[i]) {
return false; // bounds বা mismatch গেট
}
const tmp = board[r][c];
board[r][c] = "#"; // CHOOSE: visited mark
const found = go(r + 1, c, i + 1) || go(r - 1, c, i + 1) ||
go(r, c + 1, i + 1) || go(r, c - 1, i + 1); // 4 দিকে EXPLORE
board[r][c] = tmp; // UN-CHOOSE: mark সরাও
return found;
};
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (go(r, c, 0)) return true; // প্রতিটা cell-কে শুরু ধরে
}
}
return false;
}
// ---- test cases (board-এর copy পাঠাই, যেন test একে অপরকে নষ্ট না করে) ----
const b1 = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]];
const copy = (g) => g.map(row => [...row]);
assert(exist(copy(b1), "ABCCED") === true, "ABCCED");
assert(exist(copy(b1), "SEE") === true, "SEE");
assert(exist(copy(b1), "ABCB") === false, "cell পুনর্ব্যবহার নিষেধ");
assert(exist([["A"]], "A") === true, "single match");
assert(exist([["A"]], "B") === false, "single no match");
assert(exist([["A", "B"], ["C", "D"]], "ACDB") === true, "A->C->D->B বাঁক");
console.log("সব JS test pass!");
```
> **JS টীকা:** visited-set আলাদা না রেখে cell-টাকেই সাময়িক `"#"` দিয়ে mark করি, ফিরে এসে `board[r][c] = tmp` দিয়ে restore — এটাই grid-এ choose/un-choose, O(1) মেমরিতে। restore ভুললে cell চিরতরে blocked থেকে যাবে। `||` chain short-circuit করে — প্রথম দিক `true` দিলেই বাকি explore বন্ধ (শুধু "আছে কিনা" দরকার)। base case (`i === word.length`) bounds-check-এর **আগে** রাখা জরুরি, নাহলে শেষ অক্ষরে index out হতে পারে।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function exist(board: string[][], word: string): boolean {
if (!board.length || !board[0].length) return false;
const rows = board.length, cols = board[0].length;
const go = (r: number, c: number, i: number): boolean => {
if (i === word.length) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[i]) {
return false;
}
const tmp = board[r][c];
board[r][c] = "#"; // CHOOSE
const found = go(r + 1, c, i + 1) || go(r - 1, c, i + 1) ||
go(r, c + 1, i + 1) || go(r, c - 1, i + 1);
board[r][c] = tmp; // UN-CHOOSE
return found;
};
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (go(r, c, 0)) return true;
}
}
return false;
}
function expect