Word Search

Problem Statement

Given an m x n grid of characters board and a string word, return true if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where “adjacent” cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in one word.

What to notice first

• This is a backtracking problem on a 2D grid.
• Mark visited cells during DFS to avoid revisiting.
• Backtrack (unmark) when returning from recursive calls.
• Early termination if first character doesn’t match any cell.

Examples

board	word	Output	Explanation
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]	”ABCCED”	true	Path exists following adjacent cells
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]	”SEE”	true	Multiple valid paths exist
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]	”ABCB”	false	Would need to reuse ‘B’
[["a"]]	”a”	true	Single cell matches

Constraints

• m == board.length
• n == board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consist of only lowercase and uppercase English letters

Real-World Applications

Where this pattern appears

• Text editor autocomplete — find words in a dictionary with word search patterns.
• Word games — find valid words in a letter grid (Boggle, Scrabble solvers).
• Spell checking — validate word paths in cached dictionaries.
• Graph traversal — general DFS/BFS on grids with visited tracking.

Complexity Comparison

Approach	Time	Space	Notes
Backtracking (DFS)	O(NM4^L)	O(L)	Recursive; modifies board in-place
BFS with Queue	O(NM4^L)	O(N*M)	Iterative; uses explicit visited set

N = rows, M = columns, L = word length. Both have exponential time due to 4 directions per cell.

Approach 1: Backtracking (DFS) (Recommended)

★ Recommended

Use DFS with backtracking:

1. Find a starting cell matching the first character.
2. Recursively explore adjacent cells (up, down, left, right).
3. Mark visited cells temporarily to avoid revisiting within a single path.
4. Backtrack by restoring the cell’s original character.

This is efficient because it prunes branches immediately when a character doesn’t match.

⏱ Time O(N*M*4^L) Exponential due to 4 directions 💾 Space O(L) Recursion depth = word length

Step-by-step Example

Input: board = [["A","B","C"],["D","E","F"],["G","H","I"]], word = "BED"

Start: Find 'B' at (0, 1)
├─ DFS(0, 1) → 'B'
   ├─ Try (0, 0) → 'A' ✗ (not 'E')
   ├─ Try (0, 2) → 'C' ✗
   ├─ Try (1, 1) → 'E' ✓
   │  ├─ DFS(1, 1) → 'E'
   │     ├─ Try (0, 1) → marked, skip
   │     ├─ Try (1, 0) → 'D' ✓
   │     │  ├─ DFS(1, 0) → 'D'
   │     │     ├─ Reached end of word → return True

Pseudocode

function exist(board, word):
    for row in range(len(board)):
        for col in range(len(board[0])):
            if board[row][col] == word[0]:
                if dfs(board, word, row, col, 0):
                    return True
    return False

function dfs(board, word, row, col, index):
    if index == len(word):
        return True

    if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]):
        return False

    if board[row][col] != word[index] or board[row][col] == '*':
        return False

    // Mark as visited
    original = board[row][col]
    board[row][col] = '*'

    // Explore 4 directions
    found = dfs(board, word, row+1, col, index+1) or
            dfs(board, word, row-1, col, index+1) or
            dfs(board, word, row, col+1, index+1) or
            dfs(board, word, row, col-1, index+1)

    // Backtrack
    board[row][col] = original

    return found

Solution Code

Python

word_search_backtracking.py

from typing import List

def exist(board: List[List[str]], word: str) -> bool:
    """Backtracking approach: O(N*M*4^L) time, O(L) space"""
    if not board:
        return False

    def backtrack(row, col, index):
        if index == len(word):
            return True
        if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]):
            return False
        if board[row][col] != word[index]:
            return False

        board[row][col] = "#"
        found = (backtrack(row + 1, col, index + 1) or
                 backtrack(row - 1, col, index + 1) or
                 backtrack(row, col + 1, index + 1) or
                 backtrack(row, col - 1, index + 1))
        board[row][col] = word[index]
        return found

    for i in range(len(board)):
        for j in range(len(board[0])):
            if backtrack(i, j, 0):
                return True
    return False

C++

word_search_backtracking.cpp

#include <vector>
#include <string>
using namespace std;

bool exist(vector<vector<char>>& board, string word) {
    function<bool(int, int, int)> backtrack = [&](int row, int col, int index) {
        if (index == word.length()) return true;
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size()) return false;
        if (board[row][col] != word[index]) return false;

        board[row][col] = '#';
        bool found = (backtrack(row + 1, col, index + 1) ||
                      backtrack(row - 1, col, index + 1) ||
                      backtrack(row, col + 1, index + 1) ||
                      backtrack(row, col - 1, index + 1));
        board[row][col] = word[index];
        return found;
    };

    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[0].size(); j++) {
            if (backtrack(i, j, 0)) return true;
        }
    }
    return false;
}

Java

WordSearchBacktracking.java

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || word == null || word.length() == 0) {
            return false;
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

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

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

        // Mark as visited
        char original = board[row][col];
        board[row][col] = '*';

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

        // Unmark (backtrack)
        board[row][col] = original;

        return found;
    }
}

JavaScript

word_search_backtracking.js

function exist(board, word) {
    if (!board || !board.length) return false;

    function backtrack(row, col, index) {
        if (index === word.length) return true;
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) return false;
        if (board[row][col] !== word[index]) return false;

        board[row][col] = '#';
        const found = backtrack(row + 1, col, index + 1) ||
                      backtrack(row - 1, col, index + 1) ||
                      backtrack(row, col + 1, index + 1) ||
                      backtrack(row, col - 1, index + 1);
        board[row][col] = word[index];
        return found;
    }

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (backtrack(i, j, 0)) return true;
        }
    }
    return false;
}

Rust

word_search_backtracking.rs

pub fn exist(board: &mut Vec<Vec<char>>, word: String) -> bool {
    if board.is_empty() { return false; }

    fn backtrack(board: &mut Vec<Vec<char>>, word: &str, row: usize, col: usize, index: usize) -> bool {
        if index == word.len() { return true; }
        if row >= board.len() || col >= board[0].len() { return false; }
        if board[row][col] != word.chars().nth(index).unwrap() { return false; }

        board[row][col] = '#';
        let found = (row > 0 && backtrack(board, word, row - 1, col, index + 1)) ||
                    (row + 1 < board.len() && backtrack(board, word, row + 1, col, index + 1)) ||
                    (col > 0 && backtrack(board, word, row, col - 1, index + 1)) ||
                    (col + 1 < board[0].len() && backtrack(board, word, row, col + 1, index + 1));
        board[row][col] = word.chars().nth(index).unwrap();
        found
    }

    for i in 0..board.len() {
        for j in 0..board[0].len() {
            if backtrack(board, &word, i, j, 0) { return true; }
        }
    }
    false
}

Go

word_search_backtracking.go

package main

func exist(board [][]byte, word string) bool {
    if len(board) == 0 { return false }

    var backtrack func(int, int, int) bool
    backtrack = func(row, col, index int) bool {
        if index == len(word) { return true }
        if row < 0 || row >= len(board) || col < 0 || col >= len(board[0]) { return false }
        if board[row][col] != word[index] { return false }

        board[row][col] = '#'
        found := backtrack(row+1, col, index+1) ||
                 backtrack(row-1, col, index+1) ||
                 backtrack(row, col+1, index+1) ||
                 backtrack(row, col-1, index+1)
        board[row][col] = word[index]
        return found
    }

    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            if backtrack(i, j, 0) { return true }
        }
    }
    return false
}

Approach 2: BFS with Queue

✓ Simple

Use BFS with an explicit visited set instead of modifying the board. Each queue entry contains (row, col, current index in word). Explore level by level, tracking visited states.

This approach is cleaner for problems where you shouldn’t modify the input, but uses O(N*M) extra space.

⏱ Time O(N*M*4^L) Same exponential search 💾 Space O(N*M) Visited set for all cells

Step-by-step Example

Input: board = [["A","B"],["C","D"]], word = "BA"

Queue: [(0, 1, 0)]  // Start at 'B', index 0
Visited: {(0,1)}

Process (0, 1, 0):
  Current: 'B', word[0] = 'B' ✓
  Neighbors: (0,0)→'A', (1,1)→'D'
  Add (0, 0, 1) to queue (matches word[1]='A')
  Visited: {(0,1), (0,0)}

Process (0, 0, 1):
  Current: 'A', word[1] = 'A' ✓
  Index 1 == word.length - 1 → return True

Pseudocode

function exist(board, word):
    for row in range(len(board)):
        for col in range(len(board[0])):
            if board[row][col] == word[0]:
                if bfs(board, word, row, col):
                    return True
    return False

function bfs(board, word, startRow, startCol):
    queue = [(startRow, startCol, 0)]
    visited = {(startRow, startCol)}
    directions = [(0,1), (0,-1), (1,0), (-1,0)]

    while queue:
        row, col, index = queue.pop(0)

        if index == len(word) - 1:
            return True

        for dr, dc in directions:
            newRow, newCol = row + dr, col + dc
            state = (newRow, newCol)

            if 0 <= newRow < len(board) and 0 <= newCol < len(board[0]):
                if board[newRow][newCol] == word[index+1] and state not in visited:
                    visited.add(state)
                    queue.append((newRow, newCol, index+1))

    return False

Solution Code

Python

word_search_bfs.py

from typing import List
from collections import deque

def exist(board: List[List[str]], word: str) -> bool:
    """BFS approach: O(N*M*4^L) time, O(N*M) space"""
    if not board:
        return False

    for i in range(len(board)):
        for j in range(len(board[0])):
            if bfs(board, word, i, j):
                return True
    return False

def bfs(board, word, start_row, start_col):
    queue = deque([(start_row, start_col, 0, set())])
    while queue:
        row, col, index, visited = queue.popleft()
        if index == len(word):
            return True
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = row + dr, col + dc
            if 0 <= nr < len(board) and 0 <= nc < len(board[0]):
                if board[nr][nc] == word[index] and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    queue.append((nr, nc, index + 1, visited.copy()))
    return False

C++

word_search_bfs.cpp

#include <vector>
#include <string>
#include <queue>
#include <set>
using namespace std;

bool exist(vector<vector<char>>& board, string word) {
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[0].size(); j++) {
            if (board[i][j] == word[0]) {
                queue<tuple<int, int, int, set<pair<int, int>>>> q;
                set<pair<int, int>> visited;
                visited.insert({i, j});
                q.push({i, j, 1, visited});

                while (!q.empty()) {
                    auto [row, col, idx, vis] = q.front();
                    q.pop();
                    if (idx == word.length()) return true;

                    int dirs[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
                    for (auto& d : dirs) {
                        int nr = row + d[0], nc = col + d[1];
                        if (nr >= 0 && nr < board.size() && nc >= 0 && nc < board[0].size() &&
                            board[nr][nc] == word[idx] && vis.find({nr, nc}) == vis.end()) {
                            auto newVis = vis;
                            newVis.insert({nr, nc});
                            q.push({nr, nc, idx + 1, newVis});
                        }
                    }
                }
            }
        }
    }
    return false;
}

Java

WordSearchBFS.java

import java.util.*;

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || word == null || word.length() == 0) {
            return false;
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0) && bfs(board, word, i, j)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean bfs(char[][] board, String word, int startRow, int startCol) {
        Queue<int[]> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(new int[]{startRow, startCol, 0});
        visited.add(startRow + "," + startCol);

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

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0], col = current[1], index = current[2];

            if (index == word.length() - 1) {
                return true;
            }

            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                String state = newRow + "," + newCol;

                if (newRow >= 0 && newRow < board.length &&
                    newCol >= 0 && newCol < board[0].length &&
                    board[newRow][newCol] == word.charAt(index + 1) &&
                    !visited.contains(state)) {

                    visited.add(state);
                    queue.offer(new int[]{newRow, newCol, index + 1});
                }
            }
        }

        return false;
    }
}

JavaScript

word_search_bfs.js

function exist(board, word) {
    function bfs(startRow, startCol) {
        const queue = [[startRow, startCol, 0, new Set()]];
        while (queue.length) {
            const [row, col, index, visited] = queue.shift();
            if (index === word.length) return true;
            const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
            for (const [dr, dc] of dirs) {
                const nr = row + dr, nc = col + dc;
                const key = nr * 100 + nc;
                if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length &&
                    board[nr][nc] === word[index] && !visited.has(key)) {
                    const newVis = new Set(visited);
                    newVis.add(key);
                    queue.push([nr, nc, index + 1, newVis]);
                }
            }
        }
        return false;
    }
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (bfs(i, j)) return true;
        }
    }
    return false;
}

Rust

word_search_bfs.rs

use std::collections::{HashSet, VecDeque};

pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {
    for i in 0..board.len() {
        for j in 0..board[0].len() {
            if bfs(&board, &word, i, j) { return true; }
        }
    }
    false
}

fn bfs(board: &Vec<Vec<char>>, word: &str, start_row: usize, start_col: usize) -> bool {
    let mut queue = VecDeque::new();
    queue.push_back((start_row, start_col, 0, HashSet::new()));

    while let Some((row, col, index, visited)) = queue.pop_front() {
        if index == word.len() { return true; }
        let dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)];
        for (dr, dc) in dirs {
            let nr = (row as i32 + dr) as usize;
            let nc = (col as i32 + dc) as usize;
            if nr < board.len() && nc < board[0].len() &&
               board[nr][nc] == word.chars().nth(index).unwrap() && !visited.contains(&(nr, nc)) {
                let mut newVis = visited.clone();
                newVis.insert((nr, nc));
                queue.push_back((nr, nc, index + 1, newVis));
            }
        }
    }
    false
}

Go

word_search_bfs.go

package main

import "container/list"

func exist(board [][]byte, word string) bool {
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            if bfs(board, word, i, j) { return true }
        }
    }
    return false
}

func bfs(board [][]byte, word string, startRow, startCol int) bool {
    queue := list.New()
    visited := make(map[string]bool)
    queue.PushBack([3]interface{}{startRow, startCol, 0})

    for queue.Len() > 0 {
        elem := queue.Front()
        queue.Remove(elem)
        state := elem.Value.([3]interface{})
        row, col, index := state[0].(int), state[1].(int), state[2].(int)

        if index == len(word) { return true }

        dirs := [4][2]int{{0,1}, {0,-1}, {1,0}, {-1,0}}
        for _, d := range dirs {
            nr, nc := row+d[0], col+d[1]
            if nr >= 0 && nr < len(board) && nc >= 0 && nc < len(board[0]) &&
               board[nr][nc] == word[index] {
                queue.PushBack([3]interface{}{nr, nc, index + 1})
            }
        }
    }
    return false
}

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

word_search_space_optimized.py

"""
Solution for Word Search
"""

def solve():
    """Implementation for approach 3 of Word Search"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

word_search_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Word Search
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

WordSearchSpaceOptimized.java

/**
 * Solution for Word Search
 * Approach 3
 */
public class WordSearchSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

word_search_space_optimized.js

/**
 * Solution for Word Search
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

word_search_space_optimized.rs

/// Solution for Word Search
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

word_search_space_optimized.go

package main

import "fmt"

// Solution for Word Search
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Forgetting to mark visited cells: Without marking, the algorithm revisits cells and finds false paths.
• Not backtracking properly: Restore the original character after recursion; don’t leave it marked.
• Boundary checks: Ensure 0 <= row < m and 0 <= col < n before accessing board[row][col].
• Off-by-one in word indexing: The recursion index matches the character being checked, not the next character.

Interview Tips

Key trade-offs to discuss

• Backtracking vs. BFS: Backtracking is more space-efficient (O(L)) but modifies the board. BFS preserves input but uses O(N*M) space.
• Why mark visited in backtracking? Within a single DFS path, you can’t revisit the same cell; marking prevents this.
• Early termination: If you find the word starting from any cell, return immediately—no need to check other starts.
• Follow-up: Word Search II (find all words)—use a Trie for efficiency instead of checking each word separately.