DEV Community

Dev Cookies
Dev Cookies

Posted on

Blog 6: Word Search & Grid-Based Backtracking🧩

Backtracking really shines when problems involve navigating a 2D grid, making decisions at each step, and exploring multiple paths.
One of the most common categories here: Word Search and related grid exploration puzzles.

🔹 Problem Definition: Word Search (LeetCode 79)

Given an m x n grid of characters and a word, check if the word exists in the grid.

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

📌 Example:

Board = A B C E S F C S A D E E Word = "ABCCED" → true Word = "SEE" → true Word = "ABCB" → false
Enter fullscreen mode Exit fullscreen mode

🔹 Intuition

  • Start from every cell that matches the first letter.
  • From each cell, try moving in 4 directions.
  • Mark visited cells to avoid reuse.
  • If we reach the last character → success.
  • If all paths fail → word not found.

👉 This is a DFS with backtracking problem.

🔹 Java Implementation 

public class WordSearch { private int rows, cols; private char[][] board; private String word; public boolean exist(char[][] board, String word) { this.rows = board.length; this.cols = board[0].length; this.board = board; this.word = word; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (dfs(i, j, 0)) return true; } } return false; } private boolean dfs(int r, int c, int index) { if (index == word.length()) return true; if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != word.charAt(index)) return false; char temp = board[r][c]; board[r][c] = '#'; // mark visited boolean found = dfs(r + 1, c, index + 1) || dfs(r - 1, c, index + 1) || dfs(r, c + 1, index + 1) || dfs(r, c - 1, index + 1); board[r][c] = temp; // backtrack return found; } }
Enter fullscreen mode Exit fullscreen mode

🔹 Dry Run Example

Word = "ABCCED"

  • Start from A(0,0) → B(0,1) → C(0,2) → C(1,2) → E(2,2) → D(2,1) → ✅ success.
  • Backtracking ensures we explore all possibilities without revisiting cells.

🔹 Complexity Analysis

  • Time: O(M * N * 4^L)

    • M, N = grid size, L = word length.
    • Each step can branch into 4 directions.

  • Space: O(L) recursion depth + visited cells marking.

🔹 Variations of Grid-Based Backtracking

1. Word Search II (LeetCode 212)

  • Instead of a single word, find multiple words from a dictionary.
  • Use a Trie + Backtracking to prune searches efficiently. 
class WordSearchII { private Set<String> result = new HashSet<>(); private boolean[][] visited; private int rows, cols; public List<String> findWords(char[][] board, String[] words) { TrieNode root = buildTrie(words); rows = board.length; cols = board[0].length; visited = new boolean[rows][cols]; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { dfs(board, i, j, root, ""); } } return new ArrayList<>(result); } private void dfs(char[][] board, int r, int c, TrieNode node, String path) { if (r < 0 || c < 0 || r >= rows || c >= cols || visited[r][c]) return; char ch = board[r][c]; if (!node.children.containsKey(ch)) return; visited[r][c] = true; node = node.children.get(ch); String newPath = path + ch; if (node.isWord) result.add(newPath); dfs(board, r + 1, c, node, newPath); dfs(board, r - 1, c, node, newPath); dfs(board, r, c + 1, node, newPath); dfs(board, r, c - 1, node, newPath); visited[r][c] = false; } private TrieNode buildTrie(String[] words) { TrieNode root = new TrieNode(); for (String word : words) { TrieNode node = root; for (char c : word.toCharArray()) { node.children.putIfAbsent(c, new TrieNode()); node = node.children.get(c); } node.isWord = true; } return root; } static class TrieNode { Map<Character, TrieNode> children = new HashMap<>(); boolean isWord = false; } }
Enter fullscreen mode Exit fullscreen mode

2. Rat in a Maze

  • Start at top-left, reach bottom-right.
  • Only move down or right.
  • Classic recursion + backtracking problem.

3. Knight’s Tour (Chessboard)

  • Place knight at starting cell, visit all cells exactly once.
  • Backtracking + heuristics (Warnsdorff’s rule).

4. Sudoku Solver (LeetCode 37)

  • Fill a 9x9 board with digits 1–9 such that each row, column, and subgrid is valid.
  • Try filling empty cells → recurse → backtrack on failure.

🔹 Key Takeaways

✅ Grid-based backtracking problems are DFS search problems.
✅ Mark visited cells → recurse → backtrack to restore state.
✅ Use Trie for multi-word optimizations (Word Search II).
✅ Advanced problems: Sudoku Solver, Knight’s Tour, Rat in a Maze.

Top comments (0)