Leetcode -79. Word Search

The Word Search problem is a classic interview question that tests recursion, grid traversal, and backtracking. In this blog, we’ll solve it two ways:

1. Using a Set to track visited cells (clear and beginner-friendly).
2. Using an in-place optimization (cleaner and space-efficient).

---

📌 Problem Statement

We are given a 2D board of characters and a word. We need to check if the word exists in the board.

Rules:

• The word can be constructed from letters of adjacent cells (up, down, left, right).
• A cell cannot be used more than once in the same path.

Example:

Board:
A B C E
S F C S
A D E E

Word: "ABCCED"
Output: true

---

💡 Approach 1: Using a Set

The idea is simple:

1. Try every cell (r, c) as a potential starting point.
2. Use DFS to explore neighbors.
3. Keep a Set of visited cells (so we don’t revisit them).
4. Backtrack: after exploring, remove the cell from the Set.

---

✅ Code (with Set)

var exist = function (board, word) {
    let rows = board.length;
    let cols = board[0].length;
    let pathSet = new Set();

    const backtrack = (i, r, c) => {
        if (i === word.length) return true;

        if (r < 0 || c < 0 || r >= rows || c >= cols ||
            board[r][c] !== word[i] ||
            pathSet.has(r + "," + c)) {
            return false;
        }

        pathSet.add(r + "," + c);

        let res = backtrack(i + 1, r + 1, c) ||
                  backtrack(i + 1, r - 1, c) ||
                  backtrack(i + 1, r, c + 1) ||
                  backtrack(i + 1, r, c - 1);

        pathSet.delete(r + "," + c); // backtrack cleanup

        return res;
    };

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (backtrack(0, r, c)) return true;
        }
    }
    return false;
};

---

⚙️ Complexity (Set version)

• Time Complexity:

  • Worst case: O(rows × cols × 4^L) where L = length of the word.

• Space Complexity:

  • The Set stores up to L cells.
  • Recursion depth = L.
  • So O(L) extra space.

This is intuitive and great for understanding recursion, but we can do better.

---

💡 Approach 2: Optimized In-Place Marking

Instead of maintaining a Set, we can modify the board in-place:

1. At each step, temporarily set the current cell to "#" to mark it visited.
2. Explore neighbors.
3. Restore the original character when backtracking.

This way, “visited check” happens naturally because a "#" will never match the next character in word.

---

✅ Code (in-place optimization)

var exist = function (board, word) {
    let rows = board.length;
    let cols = board[0].length;

    const backtrack = (i, r, c) => {
        if (i === word.length) return true;

        if (r < 0 || c < 0 || r >= rows || c >= cols ||
            board[r][c] !== word[i]) {
            return false;
        }

        // Mark visited by modifying the board
        let temp = board[r][c];
        board[r][c] = "#";

        let res = backtrack(i + 1, r + 1, c) ||
                  backtrack(i + 1, r - 1, c) ||
                  backtrack(i + 1, r, c + 1) ||
                  backtrack(i + 1, r, c - 1);

        // Restore for other paths
        board[r][c] = temp;

        return res;
    };

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (backtrack(0, r, c)) return true;
        }
    }
    return false;
};

---

⚙️ Complexity (Optimized version)

• Time Complexity: Still O(rows × cols × 4^L).
• Space Complexity: Only recursion depth → O(L). No Set, no extra storage. Cleaner and faster.

---

🔑 Comparison

Feature	With Set	In-place Optimization
Clarity	✅ Easy to follow	⚡ Cleaner, shorter
Extra Space	O(L) (Set)	O(1) extra
Speed	Slightly slower	Faster in practice
Interview value	Good starter	Impressive finish

---

✨ Takeaways

• Set approach: Great for beginners, shows clear backtracking logic.
• In-place approach: Professional, space-efficient, and elegant.
• Both methods teach the importance of backtracking cleanup — the trick that makes recursion work correctly.

---

👉 In an interview, I’d start with the Set approach to explain my thought process, then optimize to the in-place version to show deeper problem-solving skills.

---