The O(n) Club: Word Search – When DFS Meets a Letter Maze

The O(n) Club: Word Search – When DFS Meets a Letter Maze

⚡ TL;DR

Take a grid of letters, try to trace your chosen word by hopping between adjacent (no, not diagonal) squares, all without revisiting your steps. The Java backtracking recipe: mark as you go, unmark when you regret everything. Here’s a caffeine-sized sample:

// Does the board contain the word?
boolean exist(char[][] board, String word) {
    // Run DFS for each spot
}

🧠 How Devs Usually Mess This Up

Picture your average dev on deadline: double-dipping tiles, treating the top-left as gospel, or throwing fancy queues at a problem that doesn’t want them. For the record:

• Each letter tile is a single-use pass—don’t loop over your own footprints.
• Your word can begin on any cell. Any. Cell. Yes, that one too.
• Bringing BFS or fancy data structures? You’re the person who brings lasagna to a pizza party. Just don’t.
• If you fail to unmark a cell on backtrack, you’ll slowly erase most of your possible answers. Oops!

🔍 What’s Actually Going On

This problem is like a drunken game of Boggle where the rules are weirdly strict and everyone forgot how diagonals work. For every cell, you ask, “Can I spell the word from here, one legit step at a time?” Dive in four directions, mark letters as you try them, then regret it and unmark when things don’t pan out. Grid-based recursion at its moodiest—and yes, your stack trace will be haunted by paths not taken.

🛠️ PseudoCode

• For each cell in the board:
  • Start a DFS for the full word.
• DFS Parameters: grid, word, index of letter, row, column.
• At each step:
  • If you matched all letters, you win.
  • If out of bounds or current letter mismatches, you fail this route.
  • Temporarily mark cell as used (hint: make it ‘#’, or whatever weirdness isn’t confused for a legit letter).
  • Explore right, left, up, and down recursively.
  • If any call works, return true in a hurry.
  • Unmark the cell before you back out of the awkward family reunion.

💻 The Code

public class WordSearch {
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(board, word, 0, r, c)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, String word, int idx, int r, int c) {
        if (idx == word.length()) return true;
        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length)
            return false;
        if (board[r][c] != word.charAt(idx)) return false;
        char save = board[r][c];
        board[r][c] = '#';
        boolean found = dfs(board, word, idx + 1, r + 1, c)
            || dfs(board, word, idx + 1, r - 1, c)
            || dfs(board, word, idx + 1, r, c + 1)
            || dfs(board, word, idx + 1, r, c - 1);
        board[r][c] = save;
        return found;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Miss an unmark and your grid is cursed for the rest of time (well, until the process dies).
• Index out of range: Classic error, classic facepalm.
• Time: Worst case is every cell, fanning out 3 ways per word letter: O(N * 3^L).
• Space: Stack frames can pile up to the word’s length, but not the full grid.

🧠 Interviewer Brain-Tattoo

“Backtracking: The art of boldly regretting every bad move—with style.”