DEV Community

Rakesh Reddy Peddamallu
Rakesh Reddy Peddamallu

Posted on

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
Enter fullscreen mode Exit fullscreen mode

💡 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;
};
Enter fullscreen mode Exit fullscreen mode

⚙️ 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;
};
Enter fullscreen mode Exit fullscreen mode

⚙️ 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.


Top comments (0)