Knowledge Guide
Home › DSA › Company Practice

medium 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.

Example 1:

Example 2:

Constraints:

Try it yourself

Try solving this question here:

✅ Solution 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.

Example 1:

  • Input: word="ABCCED", board:

      { 'A', 'B', 'C', 'E' },
  { 'S', 'F', 'C', 'S' },
  { 'A', 'D', 'E', 'E' }

  • Output: true

  • Explanation: The word exists in the board:
    -> { 'A', 'B', 'C', 'E' },
    -> { 'S', 'F', 'C', 'S' },
    -> { 'A', 'D', 'E', 'E' }

Example 2:

  • Input: word="SEE", board:

      { 'A', 'B', 'C', 'E' },
  { 'S', 'F', 'C', 'S' },
  { 'A', 'D', 'E', 'E' }

  • Output: true

  • Explanation: The word exists in the board:
    -> { 'A', 'B', 'C', 'E' },
    -> { 'S', 'F', 'C', 'S' },
    -> { 'A', 'D', 'E', 'E' }

Constraints:

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

Solution

The basic approach to solving the word search problem using backtracking is to start at the first character of the word and check all 4 adjacent cells in the grid to see if any of them match the next character of the word. If a match is found, mark the cell as visited and recursively check the next character of the word in the adjacent cells of the newly visited cell. If the entire word is found, return true. If no match is found, backtrack to the previous cell and try a different path. Repeat this process until the entire grid has been searched or the word is found.

Code

This function takes a 2D list board and a string word as input, and returns True if the word can be found in board and False otherwise. It uses a helper function dfs which takes 4 additional parameters: i and j are the current coordinates of the cell that is being visited, k is the index of the current character of the word being matched, and board and word are the inputs passed to the main function.

The dfs function uses a helper variable tmp to store the current value of the cell before it is marked as visited. This is done so that we can backtrack later. It then uses recursion to check if the next character of the word exists in the 4 adjacent cells, and it will mark the cell as visited and move to next index of the word by incrementing k by 1. If the next character is found, the function returns true, if not it backtracks to the previous cell, and continues the search in different path. If the entire word is found, the function returns True, otherwise it returns False after searching the entire grid.

java
public class Solution {

  public static boolean dfs(char[][] board, String word, int i, int j, int k) {
    // check if current coordinates are out of grid or the current cell doesn't
    // match the current character of the word
    if (
      i < 0 ||
      i >= board.length ||
      j < 0 ||
      j >= board[0].length ||
      board[i][j] != word.charAt(k)
    ) {
      return false;
    }
    // check if we have reached the end of the word
    if (k == word.length() - 1) {
      return true;
    }
    // mark the current cell as visited by replacing it with '/'
    char tmp = board[i][j];
    board[i][j] = '/';
    // check all 4 adjacent cells recursively
    boolean res =
      dfs(board, word, i + 1, j, k + 1) ||
      dfs(board, word, i - 1, j, k + 1) ||
      dfs(board, word, i, j + 1, k + 1) ||
      dfs(board, word, i, j - 1, k + 1);
    // backtrack by replacing the current cell with its original value
    board[i][j] = tmp;
    return res;
  }

  public boolean exist(char[][] board, String word) {
    for (int i = 0; i < board.length; i++) {
      for (int j = 0; j < board[0].length; j++) {
        // start the search from every cell
        if (dfs(board, word, i, j, 0)) {
          return true;
        }
      }
    }
    return false;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    // Test Case 1
    char[][] board1 = {
      { 'A', 'B', 'C', 'E' },
      { 'S', 'F', 'C', 'S' },
      { 'A', 'D', 'E', 'E' },
    };
    String word1 = "ABCCED";
    System.out.println(sol.exist(board1, word1)); // expected output: true

    // Test Case 2
    char[][] board2 = {
      { 'A', 'B', 'C', 'E' },
      { 'S', 'F', 'C', 'S' },
      { 'A', 'D', 'E', 'E' },
    };
    String word2 = "SEE";
    System.out.println(sol.exist(board2, word2)); // expected output: true

    // Test Case 3
    char[][] board3 = {
      { 'A', 'B', 'C', 'E' },
      { 'S', 'F', 'C', 'S' },
      { 'A', 'D', 'E', 'E' },
    };
    String word3 = "ABCB";
    System.out.println(sol.exist(board3, word3)); // expected output: false

    char[][] board4 = { { 'a', 'a' } };
    String word4 = "aaa";
    System.out.println(sol.exist(board4, word4)); // expected output: false

    char[][] board5 = { { 'a' } };
    String word5 = "a";
    System.out.println(sol.exist(board5, word5)); // expected output: true

    char[][] board6 = {
      { 'a', 'b', 'c', 'd', 'e' },
      { 'f', 'g', 'h', 'i', 'j' },
      { 'k', 'l', 'm', 'n', 'o' },
      { 'p', 'q', 'r', 's', 't' },
      { 'u', 'v', 'w', 'x', 'y' },
      { 'z', 'a', 'b', 'c', 'd' },
    };
    String word6 = "abcde";
    System.out.println(sol.exist(board6, word6)); // expected output: true

    char[][] board7 = {
      { 'a', 'b', 'c', 'd', 'e' },
      { 'f', 'g', 'h', 'i', 'j' },
      { 'k', 'l', 'm', 'n', 'o' },
      { 'p', 'q', 'r', 's', 't' },
      { 'u', 'v', 'w', 'x', 'y' },
      { 'z', 'a', 'b', 'c', 'd' },
    };
    String word7 = "zabcd";
    System.out.println(sol.exist(board7, word7)); // expected output: true
  }
}

Time Complexity

The overall time complexity of the algorithm is

  • : Number of cells in the board.
  • : Each cell can lead to up to 4 recursive calls (one for each direction: up, down, left, right). For a word of length (L), there are up to : possible paths to explore.

Thus, for each cell, the DFS can potentially explore : paths. Since the search starts from every cell, the overall complexity is .

Space Complexity

The space complexity of the exist function is , where is the length of the word. This is because the function uses a DFS algorithm, and the maximum depth of the recursion tree is . In other words, the maximum number of function calls that will be stored on the call stack at any point in time is .

🤖 Don't fully get this? Learn it with Claude

Stuck on Word Search? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Word Search** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Word Search** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Word Search**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Word Search**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Strobogrammatic Number IILowest Common Ancestor of a Binary →