Boggle word finder

You are in a Salesforce interview, and the interviewer places a grid of letters on the whiteboard. "Imagine this is a Boggle board," they say. "Can you write a method that finds whether a given word exists on this board by traversing adjacent cells?" This problem, also known as "Word Search" on other platforms, is a classic test of your ability to combine grid traversal with recursive backtracking. It shows up regularly at companies like Airbnb, Twitter, and Salesforce because it checks several skills at once: boundary handling, DFS, and state management through backtracking.

TL;DR

Search for a word on a Boggle board by trying every cell as a starting point and launching a recursive depth-first search from each. At every step, check bounds, visited status, and character match. Mark cells as visited while exploring, then unmark them (backtrack) after returning. The time complexity is O(N * 4^k) where N is total cells and k is word length, and space complexity is O(N) for the visited array plus recursion stack.

Why This Problem Matters

The Boggle word finder sits at the intersection of grid problems and backtracking, two categories that dominate technical interviews. If you can solve this problem cleanly, you already have the muscle memory for Number of Islands, surrounded regions, and other grid-based DFS questions. The backtracking piece adds a layer that separates it from simpler flood-fill problems, and interviewers know it.

Understanding the Problem

Given: An m x n board of characters and a target word of length k Task: Determine if the word can be constructed by traversing adjacent cells (horizontally or vertically) Constraint: Each cell may only be used once per path Return: true if the word is found, false otherwise

Here is the example board from the problem:

Loading visualization...

Searching for "HELLO" on this board returns true. The path starts at H(2,1) and moves up to E(1,1), right to L(1,2), up to L(0,2), then left to O(0,1):

Loading visualization...

Searching for "ALOHA" returns false because no valid adjacent path spells it out. Even though all the letters exist on the board, you cannot chain them through horizontal and vertical neighbors without revisiting a cell.

Edge Cases to Watch

Single-row or single-column board: Movement is restricted to one dimension
Word longer than the board: Impossible to find, should return false
Repeated characters: The visited array prevents reusing a cell within the same path
First character not on the board: Can short-circuit immediately

Solution Approach

The strategy breaks into two parts. First, try every cell on the board as a potential starting point. Second, from each starting cell, run a depth-first search that attempts to build the target word character by character.

The Four Directions

From any cell at position (r, c), there are exactly four neighbors to explore:

Loading visualization...

At each step of the DFS, we try all four directions. If the neighbor is in bounds, unvisited, and matches the next expected character, we recurse deeper.

Backtracking is the Key

Here is where many candidates trip up. After exploring all four directions from a cell, you must unmark it as visited. Why? Because that cell might be needed by a completely different path starting from a different position on the board.

Consider the trace for finding "HELLO":

Loading visualization...

If we had forgotten to unmark cells after exploring dead-end branches, the search would fail on paths that reuse cells from earlier, abandoned attempts.

DFS Recursion Tree

When you launch the search for "HELLO" starting at H(2,1), the recursion branches like this. Dead ends are marked with X, and the successful path runs down the left side:

Loading visualization...

Most branches terminate quickly because the character does not match. That early pruning is what keeps the algorithm practical despite the exponential worst case.

Implementation

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

Here is the full solution in Java:

import java.util.List;

public class Solution {
  public Boolean findWord(char[][] board, String word) {
    // Create a visited grid matching the board dimensions
    boolean[][] visited = new boolean[board.length][board[0].length];

    // Try every cell as a starting point
    for (int r = 0; r < board.length; r++) {
      for (int c = 0; c < board[0].length; c++) {
        if (search(board, word, new StringBuilder(), visited, r, c))
          return true;
      }
    }
    return false;
  }

  private Boolean search(
    char[][] board,
    String word,
    StringBuilder sb,
    boolean[][] visited,
    int r,
    int c
  ) {
    // Terminate if out of bounds, already visited,
    // too long, or last character does not match
    if (!isWithinBounds(r, c, board) ||
          visited[r][c] ||
          sb.length() > word.length() ||
          (sb.length() > 0 &&
           sb.charAt(sb.length() - 1) != word.charAt(sb.length() - 1)))
      return false;
    else {
      // Mark cell and extend the partial word
      visited[r][c] = true;
      sb.append(board[r][c]);

      // Check if we have built the complete word
      if (sb.toString().equals(word)) return true;

      // Explore all four directions
      List<List<Integer>> coordinates = allowedCoordinates(r, c);
      Boolean found =
        coordinates.stream().anyMatch(
          coordinate -> search(
            board, word, sb, visited,
            coordinate.get(0), coordinate.get(1)));

      // Backtrack: unmark and remove last character
      sb.deleteCharAt(sb.length() - 1);
      visited[r][c] = false;

      return found;
    }
  }

  private Boolean isWithinBounds(int r, int c, char[][] board) {
    return (r >= 0 && r <= board.length - 1) &&
             (c >= 0 && c <= board[0].length - 1);
  }

  private List<List<Integer>> allowedCoordinates(int r, int c) {
    return List.of(
      List.of(r - 1, c),
      List.of(r + 1, c),
      List.of(r, c - 1),
      List.of(r, c + 1)
    );
  }
}

Let me walk through the key decisions in this code.

The visited array is allocated once and shared across all search calls. Backtracking resets it correctly, so there is no need to create a fresh copy for each starting cell.

The StringBuilder accumulates the partial word as we descend. When we backtrack, we remove the last character. An alternative approach (used in the C++ and Go solutions below) tracks an index into the word instead of building a string, which avoids string allocation entirely.

Early termination happens in two places. The bounds and visited checks prevent invalid exploration. The character mismatch check (sb.charAt(sb.length() - 1) != word.charAt(sb.length() - 1)) prunes branches as soon as the path diverges from the target word.

Tracing Through the Larger Board

Here is the full 6x4 board from the test cases, with the path for "FIRECODE" highlighted:

Loading visualization...

The search finds F at (0,1), moves down to I at (1,1), continues down to R at (2,1), turns left to E at (2,0), goes down to C at (3,0), continues to O at (4,0), turns right to D at (4,1), and finally moves down to E at (5,1). Each move is horizontal or vertical, each cell is used exactly once.

Complexity Analysis

Time Complexity: O(N * 4^k)

For each of the N = m * n cells, we might launch a DFS that explores up to 4 directions at each of k levels. In the worst case, this gives O(N * 4^k). In practice, the visited checks and character mismatches prune the search tree aggressively, so the real performance is far better than the theoretical bound.

Space Complexity: O(N)

The visited array requires m * n booleans, and the recursion stack can grow up to depth k (the length of the word). Since k ≤ N, the total space is O(N).

Common Pitfalls

Forgetting to backtrack: If you mark a cell as visited but never unmark it, other paths that need that cell will silently fail. Always reset visited[r][c] = false after exploring all directions.
Checking the character match too late: If you append the character first and only check the match after recursing, you waste time exploring paths that have already diverged. Check early.
Modifying the board instead of using a visited array: Some solutions mark cells by replacing the character with a sentinel value (like #). This works but modifies the input, which interviewers sometimes flag as poor practice.
Not handling the empty word or empty board: Always clarify with your interviewer what to return for these edge cases.

Interview Tips

When you get this problem in an interview:

Clarify the movement rules: "Can I move diagonally, or only horizontally and vertically?" For standard Boggle, it is four directions. Some variants allow eight.
Draw the board: Sketch a small example (3x3) and trace a word through it. This catches misunderstandings before you start coding.
Explain backtracking upfront: "I will use DFS with backtracking. I will mark cells as visited while exploring and unmark them when I return." This tells the interviewer you understand the core technique.
Mention the index-based optimization: "Instead of building a string, I could track an index into the target word and compare characters directly. That avoids string allocation overhead." The C++ and Go solutions below use this approach.
Discuss follow-ups: "If we need to search for multiple words, a Trie-based approach would avoid redundant traversals." This shows deeper algorithmic knowledge.

Key Takeaways

Every cell on the board is a potential starting point, so the outer loop tries each one.
The DFS explores four directions at each cell, pruning immediately on boundary violations, visited cells, or character mismatches.
Backtracking (unmarking visited cells after exploration) is non-negotiable. Without it, valid paths get blocked by earlier dead ends.
The index-based approach (comparing board[r][c] == word[index] and incrementing the index) is more efficient than building a string, and worth mentioning in your interview.
This pattern transfers directly to other grid DFS problems like Number of Islands, surrounded regions, and path-finding challenges.

Practice and Related Problems

Once you are comfortable with the Boggle word finder, try these problems to solidify your grid DFS and backtracking skills:

Number of Islands (flood fill without backtracking)
Recursive string permutations (backtracking on strings)
Return all paths (path enumeration with backtracking)

This problem and hundreds more are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. Practicing grid traversal problems like this one builds the pattern recognition that turns interview questions into familiar territory.

Solutions in Other Languages

Python

class Solution:
    def find_word(self, board, word):
        visited = [[False for _ in range(len(board[0]))]
                   for _ in range(len(board))]
        for r in range(len(board)):
            for c in range(len(board[0])):
                if self.search(board, word, "", visited, r, c):
                    return True
        return False

    def search(self, board, word, partial, visited, r, c):
        if (not self.is_within_bounds(r, c, board) or
                visited[r][c] or
                len(partial) > len(word) or
                (len(partial) > 0 and
                 partial[-1] != word[len(partial) - 1])):
            return False
        else:
            visited[r][c] = True
            partial += board[r][c]
            if partial == word:
                return True
            found = (self.search(board, word, partial, visited, r + 1, c) or
                     self.search(board, word, partial, visited, r - 1, c) or
                     self.search(board, word, partial, visited, r, c + 1) or
                     self.search(board, word, partial, visited, r, c - 1))
            visited[r][c] = False
            return found

    def is_within_bounds(self, r, c, board):
        return (0 <= r <= len(board) - 1) and (0 <= c <= len(board[0]) - 1)

JavaScript

class Solution {
  findWord(board, word) {
    const visited = [...Array(board.length)]
      .map(_ => Array(board[0].length));
    for (let r = 0; r < board.length; r++) {
      for (let c = 0; c < board[0].length; c++) {
        if (this.search(board, word, "", visited, r, c))
          return true;
      }
    }
    return false;
  }

  search(board, word, partial, visited, r, c) {
    if (!this.isWithinBounds(r, c, board) ||
      visited[r][c] ||
      partial.length > word.length ||
      (partial.length > 0 &&
       partial[partial.length - 1] !== word[partial.length - 1]))
      return false;
    else {
      visited[r][c] = true;
      partial += board[r][c];
      if (partial === word) return true;
      const found = this.allowedCoordinates(r, c)
        .some(rc => this.search(
          board, word, partial, visited, rc[0], rc[1]));
      visited[r][c] = false;
      return found;
    }
  }

  isWithinBounds(r, c, board) {
    return (r >= 0 && r <= board.length - 1) &&
           (c >= 0 && c <= board[0].length - 1);
  }

  allowedCoordinates(r, c) {
    return [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]];
  }
}

TypeScript

class Solution {
  findWord(board: string[][], word: string): boolean {
    const visited: boolean[][] = Array.from(
      { length: board.length },
      () => new Array(board[0].length).fill(false)
    );
    for (let r = 0; r < board.length; r++) {
      for (let c = 0; c < board[0].length; c++) {
        if (this.search(board, word, "", visited, r, c))
          return true;
      }
    }
    return false;
  }

  private search(
    board: string[][], word: string, partial: string,
    visited: boolean[][], r: number, c: number
  ): boolean {
    if (!this.isWithinBounds(r, c, board) ||
      visited[r][c] ||
      partial.length > word.length ||
      (partial.length > 0 &&
       partial[partial.length - 1] !== word[partial.length - 1]))
      return false;
    else {
      visited[r][c] = true;
      partial += board[r][c];
      if (partial === word) return true;
      const found = this.allowedCoordinates(r, c)
        .some(rc => this.search(
          board, word, partial, visited, rc[0], rc[1]));
      visited[r][c] = false;
      return found;
    }
  }

  private isWithinBounds(
    r: number, c: number, board: string[][]
  ): boolean {
    return (r >= 0 && r <= board.length - 1) &&
           (c >= 0 && c <= board[0].length - 1);
  }

  private allowedCoordinates(r: number, c: number): number[][] {
    return [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]];
  }
}

C++

The C++ solution uses an index-based approach instead of building a string, comparing board[r][c] directly against word[index]:

#include <vector>

class Solution {
public:
  bool findWord(std::vector<std::vector<char>> &board,
                const std::string &word) {
    std::vector<std::vector<bool>> visited(
      board.size(),
      std::vector<bool>(board[0].size(), false)
    );
    for (int i = 0; i < board.size(); ++i) {
      for (int j = 0; j < board[0].size(); ++j) {
        if (search(board, word, 0, i, j, visited))
          return true;
      }
    }
    return false;
  }

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

    visited[r][c] = true;
    if (search(board, word, index + 1, r - 1, c, visited) ||
        search(board, word, index + 1, r + 1, c, visited) ||
        search(board, word, index + 1, r, c - 1, visited) ||
        search(board, word, index + 1, r, c + 1, visited))
      return true;

    visited[r][c] = false;
    return false;
  }
};

Go

package solution

func (s *Solution) FindWord(board [][]rune, word string) bool {
    if len(board) == 0 || len(board[0]) == 0 {
        return false
    }
    visited := make([][]bool, len(board))
    for i := range visited {
        visited[i] = make([]bool, len(board[0]))
    }
    for i, row := range board {
        for j := range row {
            if search(board, word, 0, i, j, visited) {
                return true
            }
        }
    }
    return false
}

var directions = [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func search(board [][]rune, word string, index, row, col int,
    visited [][]bool) bool {
    if index == len(word) {
        return true
    }
    if row < 0 || col < 0 ||
        row == len(board) || col == len(board[0]) ||
        visited[row][col] || rune(word[index]) != board[row][col] {
        return false
    }
    visited[row][col] = true
    for _, direction := range directions {
        if search(board, word, index+1,
            row+direction[0], col+direction[1], visited) {
            return true
        }
    }
    visited[row][col] = false
    return false
}

type Solution struct{}

Scala

import scala.collection.mutable

class Solution {
  def findWord(board: Array[Array[Char]], word: String): Boolean = {
    val visited = Array.ofDim[Boolean](board.length, board(0).length)
    for (r <- board.indices) {
      for (c <- board(0).indices) {
        if (search(board, word, new mutable.StringBuilder(),
                   visited, r, c))
          return true
      }
    }
    false
  }

  private def search(
    board: Array[Array[Char]], word: String,
    sb: StringBuilder, visited: Array[Array[Boolean]],
    r: Int, c: Int
  ): Boolean = {
    if (!isWithinBounds(r, c, board) ||
      visited(r)(c) ||
      sb.length() > word.length() ||
      (sb.nonEmpty &&
       sb.last != word.charAt(sb.length() - 1))) false
    else {
      visited(r)(c) = true
      sb.append(board(r)(c))
      if (sb.toString().equals(word)) return true
      val found = allowedCoordinates(r, c).exists {
        case (row, col) => search(board, word, sb, visited, row, col)
      }
      sb.deleteCharAt(sb.length - 1)
      visited(r)(c) = false
      found
    }
  }

  private def isWithinBounds(
    r: Int, c: Int, board: Array[Array[Char]]
  ): Boolean =
    (r >= 0 && r <= board.length - 1) &&
    (c >= 0 && c <= board(0).length - 1)

  private def allowedCoordinates(r: Int, c: Int): Seq[(Int, Int)] =
    Seq((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1))
}

Kotlin

class Solution {
    fun findWord(board: Array<CharArray>, word: String): Boolean {
        val visited = Array(board.size) { BooleanArray(board[0].size) }
        for (r in 0 until board.size) {
            for (c in 0 until board[0].size) {
                if (search(board, word, StringBuilder(),
                           visited, r, c))
                    return true
            }
        }
        return false
    }

    private fun search(
        board: Array<CharArray>, word: String,
        sb: StringBuilder, visited: Array<BooleanArray>,
        r: Int, c: Int
    ): Boolean {
        if (!isWithinBounds(r, c, board) ||
            visited[r][c] ||
            sb.length > word.length ||
            (sb.length > 0 &&
             sb[sb.length - 1] != word[sb.length - 1]))
            return false
        else {
            visited[r][c] = true
            sb.append(board[r][c])
            if (sb.toString() == word) return true
            val coordinates = allowedCoordinates(r, c)
            var found = coordinates.any { coordinate ->
                search(board, word, sb, visited,
                       coordinate[0], coordinate[1])
            }
            sb.deleteCharAt(sb.length - 1)
            visited[r][c] = false
            return found
        }
    }

    private fun isWithinBounds(
        r: Int, c: Int, board: Array<CharArray>
    ): Boolean {
        return (r >= 0 && r <= board.size - 1) &&
                (c >= 0 && c <= board[0].size - 1)
    }

    private fun allowedCoordinates(r: Int, c: Int): List<List<Int>> {
        return listOf(
            listOf(r - 1, c), listOf(r + 1, c),
            listOf(r, c - 1), listOf(r, c + 1)
        )
    }
}

Swift

import Foundation

class Solution {
    func findWord(_ board: [[Character]], _ word: String) -> Bool {
        var visited = Array(
            repeating: Array(repeating: false,
                             count: board[0].count),
            count: board.count)
        for r in 0..<board.count {
            for c in 0..<board[0].count {
                if search(board, word, "", &visited, r, c) {
                    return true
                }
            }
        }
        return false
    }

    private func search(
        _ board: [[Character]], _ word: String,
        _ built: String, _ visited: inout [[Bool]],
        _ r: Int, _ c: Int
    ) -> Bool {
        let wordChars = Array(word)
        if !isWithinBounds(r, c, board) ||
            visited[r][c] ||
            built.count > word.count ||
            (built.count > 0 &&
             built.last != wordChars[built.count - 1]) {
            return false
        } else {
            visited[r][c] = true
            let current = built + String(board[r][c])
            if current == word { return true }
            let coordinates = allowedCoordinates(r, c)
            let found = coordinates.contains { coordinate in
                search(board, word, current, &visited,
                       coordinate[0], coordinate[1])
            }
            visited[r][c] = false
            return found
        }
    }

    private func isWithinBounds(
        _ r: Int, _ c: Int, _ board: [[Character]]
    ) -> Bool {
        return (r >= 0 && r <= board.count - 1) &&
                (c >= 0 && c <= board[0].count - 1)
    }

    private func allowedCoordinates(_ r: Int, _ c: Int) -> [[Int]] {
        return [[r - 1, c], [r + 1, c],
                [r, c - 1], [r, c + 1]]
    }
}

Rust

pub struct Solution;

impl Solution {
    pub fn find_word(
        &self, board: Vec<Vec<char>>, word: String
    ) -> bool {
        let mut visited =
            vec![vec![false; board[0].len()]; board.len()];
        let word_chars: Vec<char> = word.chars().collect();
        for r in 0..board.len() {
            for c in 0..board[0].len() {
                if Self::search(
                    &board, &word_chars, &mut String::new(),
                    &mut visited, r as i32, c as i32
                ) {
                    return true;
                }
            }
        }
        false
    }

    fn search(
        board: &[Vec<char>], word: &[char],
        current: &mut String,
        visited: &mut Vec<Vec<bool>>, r: i32, c: i32,
    ) -> bool {
        let row = r as usize;
        let col = c as usize;
        if !Self::is_within_bounds(r, c, board)
            || visited[row][col]
            || current.len() > word.len()
            || (!current.is_empty() &&
                current.chars().last().unwrap()
                    != word[current.len() - 1])
        {
            return false;
        }
        visited[row][col] = true;
        current.push(board[row][col]);
        if current.len() == word.len() {
            let matches = current.chars()
                .zip(word.iter())
                .all(|(a, &b)| a == b);
            if matches { return true; }
        }
        let directions = Self::allowed_coordinates(r, c);
        let found = directions.iter()
            .any(|&(nr, nc)| Self::search(
                board, word, current, visited, nr, nc));
        current.pop();
        visited[row][col] = false;
        found
    }

    fn is_within_bounds(
        r: i32, c: i32, board: &[Vec<char>]
    ) -> bool {
        r >= 0 && r < board.len() as i32 &&
        c >= 0 && c < board[0].len() as i32
    }

    fn allowed_coordinates(r: i32, c: i32) -> Vec<(i32, i32)> {
        vec![(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]
    }
}

Ruby

class Solution
  def find_word(board, word)
    visited = Array.new(board.length) {
      Array.new(board[0].length, false)
    }
    board.each_with_index do |row, r|
      row.each_with_index do |_, c|
        return true if search(board, word, '', visited, r, c)
      end
    end
    false
  end

  def search(board, word, current, visited, r, c)
    return false if !within_bounds?(r, c, board) ||
                    visited[r][c] ||
                    current.length > word.length ||
                    (current.length > 0 &&
                     current[-1] != word[current.length - 1])
    visited[r][c] = true
    current = current + board[r][c]
    return true if current == word
    coordinates = allowed_coordinates(r, c)
    found = coordinates.any? { |coord|
      search(board, word, current, visited,
             coord[0], coord[1])
    }
    visited[r][c] = false
    found
  end

  def within_bounds?(r, c, board)
    (r >= 0 && r <= board.length - 1) &&
    (c >= 0 && c <= board[0].length - 1)
  end

  def allowed_coordinates(r, c)
    [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]]
  end
end

Dart

class Solution {
  bool findWord(List<List<String>> board, String word) {
    List<List<bool>> visited = List.generate(
      board.length,
      (_) => List.filled(board[0].length, false),
    );
    for (int r = 0; r < board.length; r++) {
      for (int c = 0; c < board[0].length; c++) {
        if (_search(board, word, StringBuffer(),
                    visited, r, c))
          return true;
      }
    }
    return false;
  }

  bool _search(
    List<List<String>> board, String word,
    StringBuffer sb, List<List<bool>> visited,
    int r, int c,
  ) {
    if (!_isWithinBounds(r, c, board) ||
        visited[r][c] ||
        sb.length > word.length ||
        (sb.length > 0 &&
         sb.toString()[sb.length - 1] != word[sb.length - 1])) {
      return false;
    } else {
      visited[r][c] = true;
      sb.write(board[r][c]);
      if (sb.toString() == word) return true;
      List<List<int>> coordinates =
          _allowedCoordinates(r, c);
      bool found = coordinates.any((coordinate) =>
          _search(board, word, sb, visited,
                  coordinate[0], coordinate[1]));
      String current = sb.toString();
      sb.clear();
      sb.write(current.substring(0, current.length - 1));
      visited[r][c] = false;
      return found;
    }
  }

  bool _isWithinBounds(
      int r, int c, List<List<String>> board) {
    return (r >= 0 && r <= board.length - 1) &&
        (c >= 0 && c <= board[0].length - 1);
  }

  List<List<int>> _allowedCoordinates(int r, int c) {
    return [[r - 1, c], [r + 1, c],
            [r, c - 1], [r, c + 1]];
  }
}

C#

using System.Text;
using System.Collections.Generic;

public class Solution {
    public bool FindWord(char[][] board, string word) {
        var visited = new bool[board.Length, board[0].Length];
        for (int r = 0; r < board.Length; r++) {
            for (int c = 0; c < board[0].Length; c++) {
                if (Search(board, word, new StringBuilder(),
                           visited, r, c))
                    return true;
            }
        }
        return false;
    }

    private bool Search(
        char[][] board, string word, StringBuilder sb,
        bool[,] visited, int r, int c
    ) {
        if (!IsWithinBounds(r, c, board) ||
            visited[r, c] ||
            sb.Length > word.Length ||
            (sb.Length > 0 &&
             sb[sb.Length - 1] != word[sb.Length - 1]))
            return false;
        else {
            visited[r, c] = true;
            sb.Append(board[r][c]);
            if (sb.ToString() == word) return true;
            var coordinates = AllowedCoordinates(r, c);
            bool found = false;
            foreach (var coordinate in coordinates) {
                if (Search(board, word, sb, visited,
                           coordinate[0], coordinate[1])) {
                    found = true;
                    break;
                }
            }
            sb.Remove(sb.Length - 1, 1);
            visited[r, c] = false;
            return found;
        }
    }

    private bool IsWithinBounds(
        int r, int c, char[][] board) {
        return (r >= 0 && r <= board.Length - 1) &&
                (c >= 0 && c <= board[0].Length - 1);
    }

    private List<int[]> AllowedCoordinates(int r, int c) {
        return new List<int[]> {
            new int[] { r - 1, c }, new int[] { r + 1, c },
            new int[] { r, c - 1 }, new int[] { r, c + 1 }
        };
    }
}

PHP

class Solution {
    public function findWord(array $board, string $word): bool {
        $visited = array_fill(0, count($board),
            array_fill(0, count($board[0]), false));
        for ($r = 0; $r < count($board); $r++) {
            for ($c = 0; $c < count($board[0]); $c++) {
                if ($this->search($board, $word, "",
                                  $visited, $r, $c))
                    return true;
            }
        }
        return false;
    }

    private function search(
        array $board, string $word, string $partial,
        array &$visited, int $r, int $c
    ): bool {
        if (!$this->isWithinBounds($r, $c, $board) ||
            $visited[$r][$c] ||
            strlen($partial) > strlen($word) ||
            (strlen($partial) > 0 &&
             $partial[strlen($partial) - 1]
                !== $word[strlen($partial) - 1]))
            return false;
        else {
            $visited[$r][$c] = true;
            $partial .= $board[$r][$c];
            if ($partial === $word) return true;
            $coordinates =
                $this->allowedCoordinates($r, $c);
            $found = false;
            foreach ($coordinates as $coordinate) {
                if ($this->search($board, $word, $partial,
                    $visited, $coordinate[0], $coordinate[1])) {
                    $found = true;
                    break;
                }
            }
            $visited[$r][$c] = false;
            return $found;
        }
    }

    private function isWithinBounds(
        int $r, int $c, array $board
    ): bool {
        return ($r >= 0 && $r <= count($board) - 1) &&
            ($c >= 0 && $c <= count($board[0]) - 1);
    }

    private function allowedCoordinates(
        int $r, int $c
    ): array {
        return [[$r - 1, $c], [$r + 1, $c],
                [$r, $c - 1], [$r, $c + 1]];
    }
}

Frequently Asked Questions

What is the difference between Boggle word search and a standard word search puzzle?

In a standard word search, words run in straight lines (horizontal, vertical, diagonal). In Boggle, you can change direction at every cell, moving to any adjacent cell horizontally or vertically. This means paths can snake through the grid in any pattern, making the search space much larger and requiring DFS with backtracking rather than simple linear scans.

What is the time complexity of the Boggle word finder?

The time complexity is O(N * 4^k) where N is the total number of cells (m * n) and k is the length of the target word. For each of the N starting cells, the DFS can branch into 4 directions at each step, exploring up to 4^k paths. In practice, the visited array and character mismatches prune most branches early.

Why is backtracking necessary for this problem?

Backtracking is essential because a cell that leads to a dead end on one path might be part of a valid path starting from a different direction. After exploring all directions from a cell, you must unmark it as visited so other search paths can use it. Without backtracking, you would incorrectly block valid paths.

What is the space complexity of the DFS approach?

The space complexity is O(N) where N is the total number of cells in the board. This accounts for the visited boolean array (m * n cells) and the recursion call stack, which can go as deep as the word length k. Since k is at most N (you cannot visit more cells than exist), the dominant term is O(N).

Can this problem be solved with BFS instead of DFS?

While BFS can technically work, DFS with backtracking is strongly preferred. DFS naturally follows a single path to completion before trying alternatives, making backtracking straightforward. BFS would require storing complete path state (including visited sets) for every node in the queue, resulting in much higher memory usage and more complex code.

How do you handle the visited array correctly during backtracking?

Mark the cell as visited before exploring its neighbors, then unmark it after all four directions have been explored. This ensures the cell is not revisited within the current path but remains available for other paths. A common bug is forgetting to unmark, which causes valid paths to be missed.

What are the terminating conditions for the recursive DFS?

There are four conditions that should cause an immediate return of false: the coordinates are out of bounds, the cell has already been visited in the current path, the partial string exceeds the target word length, or the most recently added character does not match the expected character at that position in the target word.

How does this problem relate to other grid DFS problems?

This problem is closely related to Number of Islands, which also uses DFS on a grid. The key difference is that Boggle requires backtracking (unmarking visited cells) because you need to find a specific path, while island counting permanently marks visited cells. The pattern of checking bounds, marking visited, and recursing in four directions is shared across both.

What optimizations can speed up the Boggle word finder?

The most effective optimization is early termination: check if the current character matches the expected character before recursing further. You can also precompute which characters exist on the board and skip starting positions that do not match the first character of the word. For multiple word searches, a Trie-based approach avoids redundant traversals.

How often does this problem appear in coding interviews?

The word search problem is a staple at companies like Airbnb, Twitter, and Salesforce. It frequently appears in medium-difficulty interview rounds because it tests multiple concepts simultaneously: grid traversal, recursion, backtracking, and boundary checking. Mastering this problem prepares you for an entire class of grid-based DFS questions.