017 — Word Search

Source

• Original source: Classic grid backtracking exercise (path-spelling a word)
• Platform: LeetCode — https://leetcode.com/problems/word-search/
• 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

1. Problem in simple words

একটা অক্ষরের grid (board) আর একটা word দেওয়া আছে। তোমার কাজ: grid-এর ভেতরে এমন একটা path আছে কিনা বলা, যেটা ধরে হাঁটলে word-এর অক্ষরগুলো পরপর মেলে। নিয়ম দুটো — পরপর অক্ষর অবশ্যই পাশাপাশি cell (উপর/নিচ/বাঁ/ডান, কোনাকুনি নয়) থেকে নিতে হবে, আর একই cell একবারের বেশি ব্যবহার করা যাবে না। থাকলে True, নাহলে False।

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 পুনর্ব্যবহার লাগত, নিষেধ)

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

6. Real-life analogy

word-search puzzle বা Boggle-এর কথা ভাবো: আঙুল দিয়ে অক্ষর ছুঁয়ে ছুঁয়ে একটা শব্দ ট্রেস করছ। নিয়ম — পাশাপাশি ঘরে যেতে হবে, আর একই ঘর এই শব্দের জন্য দুবার ছোঁয়া যাবে না। ভুল দিকে গেলে আঙুল পিছিয়ে এনে অন্য দিক চেষ্টা করো — সেটাই backtracking, আর "ছুঁয়েছি" চিহ্নটা তুলে ফেলাই un-choose।

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):

                 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 হলেই থামো।

8. Example input and output

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

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা cell-কে শুরু ধরে, প্রতি step-এ চারদিকেই অন্ধভাবে যাও — len(word) দৈর্ঘ্যের সব সম্ভাব্য path গড়ো, তারপর প্রতিটা path-এর অক্ষর word-এর সাথে মিলিয়ে দেখো।

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 + পরের অক্ষর"-এ।

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।

15. Python solution

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 থেকে শুরু হতে পারে।

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

18. Time complexity

O(m · n · 4^L) — m·nটা start cell, প্রতিটা থেকে গভীরতা L = len(word), প্রতি step-এ ≤ 4 দিক (প্রথম পদক্ষেপের পর কার্যত ≤ 3, কারণ যেখান থেকে এলাম mark করা)। অক্ষর-মিলের pruning বাস্তবে এর চেয়ে অনেক কম explore করায়।

19. Space complexity

In-place mark করায় বাড়তি O(L) — শুধু call stack-এর গভীরতা L পর্যন্ত। আলাদা visited set রাখলে worst case O(m·n) লাগত; in-place trick সেটা বাঁচায়।

20. Common mistakes

• backtrack-এ board[r][c] = tmp ফেরাতে ভুলে যাওয়া — পরের path-এ cell-টা চিরতরে blocked থেকে যায়, ভুল False।
• base case (i == len(word)) bounds-check-এর পরে রাখা — শেষ অক্ষর মেলার পর index out হয়ে ভুল হতে পারে; base case আগে রাখো।
• short-circuit না করে সব branch গুনতে থাকা — শুধু "আছে কি নেই" দরকার, প্রথম True-তেই থামো।
• visited check বাদ — একই cell বারবার ব্যবহার করে ভুলভাবে True।

21. Which basic problem this inherits from

ভিত্তি: Generate Parentheses (#15)-এর constraint backtracking (প্রতি step-এ গেট) + Hashing-এর seen-set ধারণা, এখানে in-place mark রূপে। ../patterns.md-এর grid-backtracking pattern আর ../concept.md-এর choose/explore/un-choose frame দেখো। গেটটা দুটো — অক্ষর-মিল আর visited।

22. Similar harder problems

• Word Search II (একসাথে অনেক word + trie) — https://leetcode.com/problems/word-search-ii/ (এই tracker-এর #23)
• Number of Islands (grid DFS, region গোনা) — https://leetcode.com/problems/number-of-islands/
• Sudoku Solver (constraint backtracking) — https://leetcode.com/problems/sudoku-solver/ (#22)

23. Pattern learned

Grid backtracking with in-place visited mark: প্রতিটা cell থেকে DFS শুরু করো; cell-কে সাময়িক mark করে 4 দিকে যাও, ফিরে এসে restore করো (choose → explore → un-choose); validity গেট = অক্ষর-মিল + visited — grid-এ path খোঁজার সব problem-এর কঙ্কাল।

24. Final summary

ভবিষ্যতের আমাকে: "Word Search = প্রতি cell থেকে go(r,c,i); অক্ষর মিললে mark করে 4 দিকে recurse, ফিরে unmark; base case i==len(word)।" যখনই 'grid-এ একটা path/শব্দ আছে কিনা' শুনবে — এই in-place mark grid-backtracking skeleton মনে করবে; visited-কে আলাদা না রেখে board-এই choose/un-choose করো।

25. JavaScript solution (with test cases)

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 হতে পারে।

26. TypeScript solution (with test cases)

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<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
const b1: string[][] = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]];
const copy = (g: string[][]): string[][] => g.map(row => [...row]);
expect(exist(copy(b1), "ABCCED"), true, "ABCCED");
expect(exist(copy(b1), "SEE"), true, "SEE");
expect(exist(copy(b1), "ABCB"), false, "reuse forbidden");
expect(exist([["A"]], "A"), true, "single");
expect(exist([["A", "B"], ["C", "D"]], "ACDB"), true, "turn");
console.log("সব TS test pass!");

TS টীকা: board: string[][] (string-এর 2D array) ও word: string টাইপ স্পষ্ট করে input-এর আকৃতি। go(...): boolean signature বলে প্রতিটা DFS শাখা path পাওয়া গেছে কিনা ফেরায় — এই boolean return-ই || short-circuit সম্ভব করে। string[][] mutable বলে in-place "#" mark করা যায়, আর copy helper-এ g.map(row => [...row]) দিয়ে গভীর copy পাঠাই যাতে এক test অন্যটার board নষ্ট না করে — TS এটা compile-time-এ আকৃতি-নিরাপদ রাখে।

27. কোথায় কাজে লাগে (real-world use)

• Word-search / Boggle games: grid-এ শব্দ-path খোঁজার সরাসরি প্রয়োগ।
• Maze/path solving: grid বা graph-এ একটা বৈধ path আছে কিনা DFS দিয়ে খোঁজা।
• Image flood-fill / region check: connected region বা নির্দিষ্ট pattern খোঁজা (Number of Islands-এর আত্মীয়)।
• Pathfinding with constraints: robot/game-AI-তে নিয়ম-মানা route খোঁজা (cell পুনর্ব্যবহার নিষেধ ইত্যাদি)।
• Grid-based puzzle solvers: Sudoku, crossword, nonogram — constraint backtracking-এর grid রূপ।

এক কথায়, "2D grid-এ নিয়ম-মানা একটা path/pattern আছে কিনা" শুনলেই — প্রতি cell থেকে DFS, in-place visited-mark করে choose/explore/un-choose; এটাই সব grid-backtracking-এর মূল কঙ্কাল।

---

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