Skip to content
AI360Xpert
Back to Backtracking
Medium

Word Search

Given an `m x n` grid of characters `board` and a string `word`, return `true` if `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.

Examples

Input:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output:true
The word "ABCCED" can be formed by tracing through the adjacent cells in the grid.
Input:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output:true
The word "SEE" can be found.
Input:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output:false
The word "ABCB" cannot be found, because we cannot use the same cell "B" twice.

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.

Backtracking (DFS)

Approach

We iterate through every cell in the grid. If the cell matches the first character of the word, we start a Depth-First Search (DFS) from that cell. During DFS, we check if the current cell matches the corresponding character in the word. If so, we mark the cell as visited (e.g., by changing its character to a special symbol like `#`) and recursively search its up, down, left, and right neighbors. If any path successfully matches the entire word, we return true. Otherwise, we backtrack by restoring the original character of the cell.

Complexity Analysis

Time Complexity
O(m * n * 4^L)
Space Complexity
O(L)

L is the length of the word. We might start a DFS from every cell (m * n). The DFS explores up to 4 directions at each step up to depth L. The space complexity is O(L) for the recursion stack.

Solution.java
class Solution {    public boolean exist(char[][] board, String word) {        int m = board.length;        int n = board[0].length;                // Start DFS from every cell        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 boolean dfs(char[][] board, String word, int i, int j, int index) {        // Base case: all characters found        if (index == word.length()) {            return true;        }                // Out of bounds or character mismatch        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {            return false;        }                // Mark as visited by replacing the character        char temp = board[i][j];        board[i][j] = '#';                // Explore all 4 adjacent directions        boolean 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);                                // Backtrack: restore the character        board[i][j] = temp;                return found;    }}