Grid Word Hunt

You're halfway through a Bloomberg phone screen when the interviewer shares a grid of letters on the screen. "Imagine you're playing a word puzzle game. You have this grid of characters, and you need to determine whether a specific word can be spelled out by connecting adjacent cells - up, down, left, or right. Each cell can only be used once per word. Can you write a function to solve this?" This is Grid Word Hunt, commonly known as "Word Search," and it is one of the most frequently asked backtracking problems at companies like Amazon, Bloomberg, Apple, and Adobe. It tests your ability to combine DFS traversal with backtracking on a 2D grid.

TL;DR

For each cell in the grid, attempt a DFS that matches characters of the word one by one. At each step, check bounds, verify the character matches, mark the cell as visited, and recurse in all four directions. If the full word is matched, return true. If a path fails, backtrack by unmarking the cell. This runs in O(m * n * 4^k) time where k is the word length, and O(m * n) space for the visited tracking and recursion stack.

Why This Problem Matters

Grid Word Hunt sits at the intersection of two important interview topics: grid traversal and backtracking. While simpler grid problems like Number of Islands only need a one-way flood fill, this problem requires you to undo your work when a path doesn't pan out. That backtracking step is what separates this from basic DFS. Companies test this problem frequently because it reveals whether candidates can manage mutable state across recursive calls without introducing subtle bugs.

Understanding the Problem

Given an m x n grid of characters and a target word, determine if the word can be constructed by connecting horizontally or vertically adjacent cells. Each cell may only be used once per path.

Here is the example grid:

The grid is 3 rows by 4 columns, filled with uppercase letters. The test cases ask us to check:

• exist(board, "ABCCED") returns true
• exist(board, "SEE") returns true
• exist(board, "ABCB") returns false

The constraints are small (grid up to 6x6, word up to 15 characters), but the exponential branching of DFS makes the approach matter.

Edge Cases to Consider

1. Single cell grid: [["A"]] with word "A" returns true
2. Word longer than grid cells: If the word has more characters than cells in the grid, return false immediately
3. All identical characters: Grid filled with "A" and word "AAA" - must respect the single-use-per-path constraint
4. No matching first character: If the first character of the word doesn't appear anywhere in the grid, return false

Solution Approach

Think of the grid as a maze where each cell is a room containing a letter. You're trying to walk through the maze, stepping into rooms one at a time, spelling out the word as you go. You can only move to rooms directly above, below, left, or right of your current room, and you cannot re-enter a room you've already visited on this particular walk.

The algorithm has two layers:

Outer loop: Scan every cell in the grid. If the cell's character matches the first character of the word, start a DFS from that cell.

DFS with backtracking: From the current cell, try to match the next character by exploring all four adjacent cells. If a direction leads to a match, continue deeper. If all four directions fail, backtrack by unmarking the current cell and returning false.

Walking Through "ABCCED"

Step 1: The outer loop finds A at position (0,0). This matches the first character of "ABCCED", so we start DFS.

Step 2: From (0,0), we need B. We check all four neighbors. The cell to the right, (0,1), contains B. Match. We mark (0,0) as visited and recurse to (0,1). From there, we need C and find it at (0,2).

Step 3: From (0,2) we need another C. We check neighbors: up is out of bounds, right is E (no match), left is B (no match, and it's visited). Down is (1,2) which contains C. Match. The path turns downward.

Step 4: From (1,2) we need E. Down is (2,2) = E. Match. From (2,2) we need D. Left is (2,1) = D. Match. We've matched all 6 characters. Return true.

Why "ABCB" Returns False

For the word "ABCB", DFS matches A at (0,0), B at (0,1), and C at (0,2). Now it needs a B, but the only adjacent B is at (0,1), which is already visited on this path. All other neighbors of (0,2) don't contain B. The search backtracks, unmarks cells, and tries other starting points. No valid path exists.

The DFS Call Stack

Here is how the recursive calls progress when searching for "SEE" starting from (1,3):

The first S is found at (1,3). Moving down to (2,3) matches the first E. Moving left to (2,2) matches the second E. The word is fully matched, so the recursion unwinds and returns true.

Implementation

Prefer a different language? Jump to solutions in other languages.

Here is the solution in Java:

public class Solution {

  public boolean exist(char[][] board, String word) {
    int rows = board.length;
    int cols = board[0].length;
    boolean[][] visited = new boolean[rows][cols];

    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        if (dfs(board, word, i, j, 0, visited)) {
          return true;
        }
      }
    }
    return false;
  }

  private boolean dfs(char[][] board, String word, int row, int col,
                      int index, boolean[][] visited) {
    if (index == word.length()) {
      return true;
    }

    if (row < 0 || row >= board.length || col < 0 || col >= board[0].length
        || visited[row][col] || board[row][col] != word.charAt(index)) {
      return false;
    }

    visited[row][col] = true;

    boolean found = dfs(board, word, row + 1, col, index + 1, visited) ||
                    dfs(board, word, row - 1, col, index + 1, visited) ||
                    dfs(board, word, row, col + 1, index + 1, visited) ||
                    dfs(board, word, row, col - 1, index + 1, visited);

    visited[row][col] = false;

    return found;
  }
}

The exist method iterates through every cell as a potential starting point. For each cell, it calls dfs, passing the board, the target word, the current position, the character index to match, and the visited array.

The dfs method first checks the base case: if index equals the word length, all characters have been matched, so return true. Then it checks boundary conditions, the visited flag, and character matching in a single guard clause. If the current cell is valid, it marks the cell as visited, recurses in all four directions, and then unmarks the cell (the backtracking step). The short-circuit || means that as soon as one direction finds the word, the remaining directions are skipped.

Complexity Analysis

Time Complexity: O(m * n * 4^k)

The outer loop iterates through all m * n cells. From each cell, the DFS can branch into 4 directions at each level, and the maximum depth is k (the word length). In practice, the effective branching factor is closer to 3 because you never revisit the cell you came from, and character mismatches cause early pruning. Still, the worst case is O(m \times n \times 4^k).

Space Complexity: O(m * n)

The visited array uses m * n space. The recursion stack depth is bounded by the word length k, which is at most 15 given the constraints (and at most m * n in the general case). So total space is O(m * n).

Alternative Approaches

1. In-place marking: Instead of a separate visited array, temporarily replace the character with '#' and restore it after backtracking. This saves O(m * n) space but modifies the input. The Python and JavaScript solutions below use this technique.
2. Character frequency check: Before running any DFS, count character frequencies in the grid and verify the word's characters are all present in sufficient quantities. This is a quick precheck that can reject impossible cases in O(m * n) time.
3. Reverse the word: If the last character of the word appears fewer times in the grid than the first character, reverse the word before searching. This reduces the number of DFS starting points.

Common Pitfalls

1. Forgetting to backtrack: The most common bug is marking a cell as visited but never unmarking it. Without visited[row][col] = false after the recursive calls, cells visited in one failed path stay blocked for all subsequent paths.
2. Not checking bounds before character match: Accessing board[row][col] before verifying that row and col are in bounds causes index-out-of-bounds exceptions. Always check bounds first.
3. Using global visited state across starting points: The visited array must be clean (or properly backtracked) between different starting cells. Since backtracking resets all cells after each complete DFS tree, this works naturally with a single shared array.
4. Short-circuit evaluation order: The || operator stops evaluating once a true is found. If you use | (bitwise OR) by mistake, all four directions will always be explored, wasting time and potentially causing incorrect visited state.

Interview Tips

When solving this problem in an interview:

1. Clarify adjacency: "Are diagonal moves allowed, or only horizontal and vertical?" (Answer: only horizontal and vertical for this problem.)
2. Ask about mutation: "Can I modify the board temporarily during the search?" This determines whether to use a visited array or the in-place '#' trick.
3. Draw the grid: Sketch the 3x4 example and trace through one word match, showing how the DFS path forms. This builds confidence before coding.
4. Mention the follow-up: After solving, mention Word Search II where you search for multiple words simultaneously using a Trie. This shows you understand how the problem scales.
5. Discuss optimizations: Mention the character frequency precheck and the word-reversal trick. Even if you don't implement them, awareness of these optimizations demonstrates strong problem-solving instincts.

Key Takeaways

• Grid Word Hunt requires DFS with backtracking, not just a one-way flood fill. The backtracking step (unmarking visited cells) is the critical difference from problems like Number of Islands.
• The outer loop tries every cell as a starting point. The DFS recurses in four directions, matching one character at a time. Short-circuit || stops early when the word is found.
• Time complexity is O(m * n * 4^k) in the worst case, but character mismatches and the visited constraint prune most branches in practice.
• The two implementation variants (separate visited array vs. in-place character replacement) are both valid. Choose based on whether the interviewer allows input mutation.
• Test with three scenarios: a word that exists, a word that fails due to the single-use constraint (like "ABCB"), and a word whose characters aren't present in the grid at all.

Practice Makes Perfect

Once you're comfortable with Grid Word Hunt, these related problems build on the same DFS and backtracking pattern:

• Word Search II (search for multiple words using a Trie)
• Number of Islands (simpler grid DFS without backtracking)
• Surrounded Regions (grid traversal with boundary conditions)
• Path with Maximum Gold (grid DFS collecting values with backtracking)

This problem and thousands of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. Whether you're targeting Amazon, Bloomberg, or Apple, mastering backtracking on grids will give you a strong foundation for your interview prep.

Solutions in Other Languages

Python

The Python solution uses in-place marking by replacing the current character with '#' and restoring it after exploration, avoiding a separate visited array.

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(row: int, col: int, index: int) -> bool:
            if index == len(word):
                return True
            if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]) or board[row][col] != word[index]:
                return False

            temp = board[row][col]
            board[row][col] = '#'

            found = (dfs(row + 1, col, index + 1) or
                     dfs(row - 1, col, index + 1) or
                     dfs(row, col + 1, index + 1) or
                     dfs(row, col - 1, index + 1))

            board[row][col] = temp
            return found

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0] and dfs(i, j, 0):
                    return True

        return False

JavaScript

class Solution {
  exist(board, word) {
    const rows = board.length;
    const cols = board[0].length;

    const dfs = (i, j, index) => {
      if (index === word.length) return true;
      if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] !== word[index]) return false;

      const temp = board[i][j];
      board[i][j] = '#';

      const found = dfs(i + 1, j, index + 1) ||
                    dfs(i - 1, j, index + 1) ||
                    dfs(i, j + 1, index + 1) ||
                    dfs(i, j - 1, index + 1);

      board[i][j] = temp;
      return found;
    };

    for (let i = 0; i < rows; i++) {
      for (let j = 0; j < cols; j++) {
        if (dfs(i, j, 0)) return true;
      }
    }

    return false;
  }
}

TypeScript

class Solution {
  exist(board: string[][], word: string): boolean {
    const rows = board.length;
    const cols = board[0].length;

    const dfs = (i: number, j: number, index: number): boolean => {
      if (index === word.length) return true;
      if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] !== word[index]) return false;

      const temp = board[i][j];
      board[i][j] = '#';

      const found = dfs(i + 1, j, index + 1) ||
                    dfs(i - 1, j, index + 1) ||
                    dfs(i, j + 1, index + 1) ||
                    dfs(i, j - 1, index + 1);

      board[i][j] = temp;
      return found;
    };

    for (let i = 0; i < rows; i++) {
      for (let j = 0; j < cols; j++) {
        if (dfs(i, j, 0)) return true;
      }
    }

    return false;
  }
}

C++

#include <vector>
#include <string>

class Solution {
public:
  bool exist(std::vector<std::vector<char>> &board, std::string word) {
    int m = board.size();
    int n = board[0].size();

    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (dfs(board, word, i, j, 0)) {
          return true;
        }
      }
    }
    return false;
  }

private:
  bool dfs(std::vector<std::vector<char>> &board, const std::string &word,
           int i, int j, int index) {
    if (index == word.size()) {
      return true;
    }
    if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()
        || board[i][j] != word[index]) {
      return false;
    }

    char temp = board[i][j];
    board[i][j] = '#';

    bool found = dfs(board, word, i + 1, j, index + 1) ||
                 dfs(board, word, i - 1, j, index + 1) ||
                 dfs(board, word, i, j + 1, index + 1) ||
                 dfs(board, word, i, j - 1, index + 1);

    board[i][j] = temp;

    return found;
  }
};

Go

package solution

func (s *Solution) Exist(board [][]byte, word string) bool {
    rows := len(board)
    cols := len(board[0])

    var dfs func(int, int, int) bool
    dfs = func(r, c, index int) bool {
        if index == len(word) {
            return true
        }
        if r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != word[index] {
            return false
        }

        temp := board[r][c]
        board[r][c] = '#'

        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

        return found
    }

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if dfs(i, j, 0) {
                return true
            }
        }
    }

    return false
}

type Solution struct{}

Scala

class Solution {
  def exist(board: Array[Array[Char]], word: String): Boolean = {
    def dfs(x: Int, y: Int, index: Int): Boolean = {
      if (index == word.length) return true
      if (x < 0 || x >= board.length || y < 0 || y >= board(0).length
          || board(x)(y) != word(index)) return false

      val temp = board(x)(y)
      board(x)(y) = '#'

      val found = dfs(x + 1, y, index + 1) ||
                  dfs(x - 1, y, index + 1) ||
                  dfs(x, y + 1, index + 1) ||
                  dfs(x, y - 1, index + 1)

      board(x)(y) = temp
      found
    }

    for (i <- board.indices; j <- board(i).indices) {
      if (dfs(i, j, 0)) return true
    }
    false
  }
}

Kotlin

class Solution {
  fun exist(board: Array<CharArray>, word: String): Boolean {
    val rows = board.size
    val cols = board[0].size
    val visited = Array(rows) { BooleanArray(cols) }

    for (i in 0 until rows) {
      for (j in 0 until cols) {
        if (dfs(board, word, i, j, 0, visited)) {
          return true
        }
      }
    }
    return false
  }

  private fun dfs(
    board: Array<CharArray>,
    word: String,
    row: Int,
    col: Int,
    index: Int,
    visited: Array<BooleanArray>
  ): Boolean {
    if (index == word.length) {
      return true
    }

    if (row < 0 || row >= board.size || col < 0 || col >= board[0].size
        || visited[row][col] || board[row][col] != word[index]) {
      return false
    }

    visited[row][col] = true

    val found = dfs(board, word, row + 1, col, index + 1, visited) ||
                dfs(board, word, row - 1, col, index + 1, visited) ||
                dfs(board, word, row, col + 1, index + 1, visited) ||
                dfs(board, word, row, col - 1, index + 1, visited)

    visited[row][col] = false

    return found
  }
}

Swift

import Foundation

class Solution {
    func exist(_ board: [[Character]], _ word: String) -> Bool {
        let rows = board.count
        let cols = board[0].count
        let wordChars = Array(word)
        var visited = [[Bool]](repeating: [Bool](repeating: false, count: cols), count: rows)

        for i in 0..<rows {
            for j in 0..<cols {
                if dfs(board, wordChars, i, j, 0, &visited) {
                    return true
                }
            }
        }
        return false
    }

    private func dfs(_ board: [[Character]], _ wordChars: [Character],
                     _ row: Int, _ col: Int, _ index: Int,
                     _ visited: inout [[Bool]]) -> Bool {
        if index == wordChars.count {
            return true
        }

        if row < 0 || row >= board.count || col < 0 || col >= board[0].count
            || visited[row][col] || board[row][col] != wordChars[index] {
            return false
        }

        visited[row][col] = true

        let found = dfs(board, wordChars, row + 1, col, index + 1, &visited) ||
                    dfs(board, wordChars, row - 1, col, index + 1, &visited) ||
                    dfs(board, wordChars, row, col + 1, index + 1, &visited) ||
                    dfs(board, wordChars, row, col - 1, index + 1, &visited)

        visited[row][col] = false

        return found
    }
}

Rust

pub struct Solution;

impl Solution {
    pub fn exist(&self, board: Vec<Vec<char>>, word: String) -> bool {
        let rows = board.len();
        let cols = board[0].len();
        let mut visited = vec![vec![false; cols]; rows];
        let chars: Vec<char> = word.chars().collect();

        for i in 0..rows {
            for j in 0..cols {
                if Self::dfs(&board, &chars, i, j, 0, &mut visited) {
                    return true;
                }
            }
        }
        false
    }

    fn dfs(board: &[Vec<char>], chars: &[char], row: usize, col: usize,
           index: usize, visited: &mut Vec<Vec<bool>>) -> bool {
        if index == chars.len() {
            return true;
        }

        if row >= board.len() || col >= board[0].len()
            || visited[row][col] || board[row][col] != chars[index] {
            return false;
        }

        visited[row][col] = true;

        let found = Self::dfs(board, chars, row + 1, col, index + 1, visited) ||
                    Self::dfs(board, chars, row.wrapping_sub(1), col, index + 1, visited) ||
                    Self::dfs(board, chars, row, col + 1, index + 1, visited) ||
                    Self::dfs(board, chars, row, col.wrapping_sub(1), index + 1, visited);

        visited[row][col] = false;

        found
    }
}

C#

public class Solution {
    public bool Exist(char[][] board, string word) {
        int rows = board.Length;
        int cols = board[0].Length;
        var visited = new bool[rows][];
        for (int k = 0; k < rows; k++) {
            visited[k] = new bool[cols];
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (Dfs(board, word, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private bool Dfs(char[][] board, string word, int row, int col,
                     int index, bool[][] visited) {
        if (index == word.Length) {
            return true;
        }

        if (row < 0 || row >= board.Length || col < 0 || col >= board[0].Length
            || visited[row][col] || board[row][col] != word[index]) {
            return false;
        }

        visited[row][col] = true;

        bool found = Dfs(board, word, row + 1, col, index + 1, visited) ||
                     Dfs(board, word, row - 1, col, index + 1, visited) ||
                     Dfs(board, word, row, col + 1, index + 1, visited) ||
                     Dfs(board, word, row, col - 1, index + 1, visited);

        visited[row][col] = false;

        return found;
    }
}

Dart

class Solution {
  bool exist(List<List<String>> board, String word) {
    int rows = board.length;
    int cols = board[0].length;
    List<List<bool>> visited =
        List.generate(rows, (_) => List.filled(cols, false));

    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        if (_dfs(board, word, i, j, 0, visited)) {
          return true;
        }
      }
    }
    return false;
  }

  bool _dfs(List<List<String>> board, String word, int row, int col,
      int index, List<List<bool>> visited) {
    if (index == word.length) {
      return true;
    }

    if (row < 0 || row >= board.length || col < 0 || col >= board[0].length
        || visited[row][col] || board[row][col] != word[index]) {
      return false;
    }

    visited[row][col] = true;

    bool found = _dfs(board, word, row + 1, col, index + 1, visited) ||
        _dfs(board, word, row - 1, col, index + 1, visited) ||
        _dfs(board, word, row, col + 1, index + 1, visited) ||
        _dfs(board, word, row, col - 1, index + 1, visited);

    visited[row][col] = false;

    return found;
  }
}

PHP

<?php

class Solution {
    public function exist(array $board, string $word): bool {
        $rows = count($board);
        $cols = count($board[0]);
        $visited = array_fill(0, $rows, array_fill(0, $cols, false));

        for ($i = 0; $i < $rows; $i++) {
            for ($j = 0; $j < $cols; $j++) {
                if ($this->dfs($board, $word, $i, $j, 0, $visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private function dfs(array &$board, string $word, int $row, int $col,
                         int $index, array &$visited): bool {
        if ($index === strlen($word)) {
            return true;
        }

        if ($row < 0 || $row >= count($board) || $col < 0 || $col >= count($board[0])
            || $visited[$row][$col] || $board[$row][$col] !== $word[$index]) {
            return false;
        }

        $visited[$row][$col] = true;

        $found = $this->dfs($board, $word, $row + 1, $col, $index + 1, $visited) ||
                 $this->dfs($board, $word, $row - 1, $col, $index + 1, $visited) ||
                 $this->dfs($board, $word, $row, $col + 1, $index + 1, $visited) ||
                 $this->dfs($board, $word, $row, $col - 1, $index + 1, $visited);

        $visited[$row][$col] = false;

        return $found;
    }
}

Ruby

class Solution
  def exist(board, word)
    rows = board.length
    cols = board[0].length
    visited = Array.new(rows) { Array.new(cols, false) }

    (0...rows).each do |i|
      (0...cols).each do |j|
        if dfs(board, word, i, j, 0, visited)
          return true
        end
      end
    end
    false
  end

  def dfs(board, word, row, col, index, visited)
    if index == word.length
      return true
    end

    if row < 0 || row >= board.length || col < 0 || col >= board[0].length ||
       visited[row][col] || board[row][col] != word[index]
      return false
    end

    visited[row][col] = true

    found = dfs(board, word, row + 1, col, index + 1, visited) ||
            dfs(board, word, row - 1, col, index + 1, visited) ||
            dfs(board, word, row, col + 1, index + 1, visited) ||
            dfs(board, word, row, col - 1, index + 1, visited)

    visited[row][col] = false

    found
  end
end