Word Search

Med

#0079Time: O(N * M * 3^L), where N and M are the dimensions of the board, and L is the length of the word. We iterate through N * M cells. The DFS from each cell can go up to L levels deep. At each level (except the first), there are at most 3 directions to explore.Space: O(L), where L is the length of the word. This space is used by the recursion stack.34 companies

Patterns

Backtracking

Algorithms

Depth-First Search

Data structures

Array String Matrix

Companies

Adobe Amazon Apple Atlassian

Prompt

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.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

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.

Follow up: Could you use search pruning to make your solution faster with a larger board?

Approaches

2 approaches with complexity analysis and trade-offs.

This approach treats the 2D grid as a graph where adjacent cells are connected. The problem then becomes finding a path in this graph that spells out the given word. We can use Depth-First Search (DFS) combined with backtracking to explore all possible paths starting from each cell.

Algorithm

Iterate through each cell (i, j) in the board.
If board[i][j] matches the first character of word, call a recursive helper function dfs(i, j, 0) to start the search.
If the helper function returns true, the word is found, so return true immediately.
If the loops complete without finding the word, return false.
Inside the dfs(row, col, index) function:
- Base Case 1: If index equals word.length(), it means we have successfully matched all characters. Return true.
- Base Case 2: If the current coordinates (row, col) are out of the board's bounds, or if board[row][col] does not match word.charAt(index), this path is invalid. Return false.
- Recursive Step:
  - a. Mark the current cell as visited to avoid cycles. For example, char temp = board[row][col]; board[row][col] = '#';
  - b. Explore the four adjacent neighbors (up, down, left, right) by calling dfs for each with index + 1.
  - c. If any of the four recursive calls return true, set a found flag to true.
- Backtrack:
  - a. Restore the original character of the cell: board[row][col] = temp;
  - b. Return the found flag.

Walkthrough

The core of the solution is a recursive DFS function that explores paths. We iterate through every cell of the board. If a cell's character matches the first character of the word, we initiate a DFS from that cell.

The DFS function, let's call it search(row, col, index), tries to find the rest of the word starting from word.charAt(index) at the grid position (row, col).

To prevent using the same letter cell more than once in a single path, we mark the current cell as visited before exploring its neighbors. A common technique is to temporarily modify the character in the board at the current position (e.g., to '#'). After the recursive calls for its neighbors return, we must backtrack by restoring the cell's original character. This ensures the cell is available for other paths that might start from a different initial cell.

The search proceeds in 4 directions (up, down, left, right). If any of these recursive searches find the complete word, we return true. If all paths from a starting cell are exhausted without finding the word, we continue the search from the next potential starting cell in the grid.

Here is the implementation in Java:

1class Solution {2    public boolean exist(char[][] board, String word) {3        int m = board.length;4        int n = board[0].length;5 6        for (int i = 0; i < m; i++) {7            for (int j = 0; j < n; j++) {8                // Start search only if the first character matches9                if (board[i][j] == word.charAt(0) && dfs(board, word, i, j, 0)) {10                    return true;11                }12            }13        }14        return false;15    }16 17    private boolean dfs(char[][] board, String word, int r, int c, int index) {18        // Base case: Successfully found the entire word19        if (index == word.length()) {20            return true;21        }22 23        // Boundary checks and character match check24        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(index)) {25            return false;26        }27 28        // Mark the current cell as visited to avoid using it again in the same path29        char temp = board[r][c];30        board[r][c] = '#'; 31 32        // Explore all 4 adjacent cells33        boolean found = dfs(board, word, r + 1, c, index + 1) ||34                        dfs(board, word, r - 1, c, index + 1) ||35                        dfs(board, word, r, c + 1, index + 1) ||36                        dfs(board, word, r, c - 1, index + 1);37 38        // Backtrack: Restore the cell's original character39        board[r][c] = temp;40 41        return found;42    }43}

Complexity

Time

O(N * M * 3^L), where N and M are the dimensions of the board, and L is the length of the word. We iterate through N * M cells. The DFS from each cell can go up to L levels deep. At each level (except the first), there are at most 3 directions to explore.

Space

O(L), where L is the length of the word. This space is used by the recursion stack.

Trade-offs

Pros

Conceptually straightforward, applying a standard graph traversal algorithm.
Correctly handles the constraint of not reusing cells via backtracking.
Sufficiently efficient for the given problem constraints.

Cons

The time complexity is exponential in the length of the word, which can be slow for larger inputs.
May perform unnecessary searches if the starting character of the word is very common on the board.

This approach enhances the standard backtracking algorithm by incorporating pruning techniques. Pruning helps to eliminate non-viable search paths early, which can significantly improve performance in practice, especially on larger boards or when there's a clear mismatch between the word's character requirements and the board's character availability.

Algorithm

Pruning Step 1: If word.length() > m * n, return false.
Pruning Step 2: Count character frequencies on the board and in the word. If count_board(c) < count_word(c) for any character c, return false.
Pruning Step 3 (Heuristic): Compare the frequency of the first and last characters of the word on the board. If the last character is less frequent, reverse the word to reduce the number of search starting points.
Main Search: Proceed with the same DFS backtracking algorithm as the previous approach, iterating through the board to find starting cells that match the (potentially reversed) word's first character.

Walkthrough

Before starting the expensive DFS traversal, we can perform a few quick checks to see if a solution is even possible.

First, a simple check: if the length of the word is greater than the total number of cells in the board, it's impossible to form the word, so we can return false immediately.

Second, a more powerful check involves character frequencies. We can count the occurrences of each character required by the word and compare them against the character counts on the board. If the board doesn't have enough of a specific character needed for the word, we can again return false without any searching.

Finally, we can add a heuristic to guide the search. The number of starting points for our DFS is determined by the number of occurrences of the first character of the word. If the last character of the word is rarer on the board than the first character, it's more efficient to search for the word in reverse. This reduces the number of top-level DFS calls. After these pruning steps, we proceed with the same DFS and backtracking logic as the basic approach.

Here is an implementation that includes these pruning steps:

1class Solution {2    public boolean exist(char[][] board, String word) {3        int m = board.length;4        int n = board[0].length;5 6        // Pruning 1: Word length7        if (word.length() > m * n) {8            return false;9        }10 11        // Pruning 2 & 3 setup: Count character frequencies on the board12        int[] boardCounts = new int[128]; // Assuming ASCII characters13        for (int i = 0; i < m; i++) {14            for (int j = 0; j < n; j++) {15                boardCounts[board[i][j]]++;16            }17        }18 19        // Pruning 2: Check if board has enough characters for the word20        int[] wordCounts = new int[128];21        for (char c : word.toCharArray()) {22            wordCounts[c]++;23        }24        for (int i = 0; i < 128; i++) {25            if (wordCounts[i] > boardCounts[i]) {26                return false;27            }28        }29 30        // Pruning 3: Search from the rarer end of the word31        if (boardCounts[word.charAt(0)] > boardCounts[word.charAt(word.length() - 1)]) {32            word = new StringBuilder(word).reverse().toString();33        }34 35        // Main DFS loop36        for (int i = 0; i < m; i++) {37            for (int j = 0; j < n; j++) {38                if (board[i][j] == word.charAt(0) && dfs(board, word, i, j, 0)) {39                    return true;40                }41            }42        }43        return false;44    }45 46    private boolean dfs(char[][] board, String word, int r, int c, int index) {47        if (index == word.length()) return true;48        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(index)) return false;49        50        char temp = board[r][c];51        board[r][c] = '#'; // Mark as visited52        53        boolean found = dfs(board, word, r + 1, c, index + 1) ||54                        dfs(board, word, r - 1, c, index + 1) ||55                        dfs(board, word, r, c + 1, index + 1) ||56                        dfs(board, word, r, c - 1, index + 1);57        58        board[r][c] = temp; // Backtrack59        return found;60    }61}

Complexity

Time

O(N * M * 3^L). The worst-case asymptotic complexity remains the same as the basic approach because the pruning steps might not eliminate any paths in some cases. However, the practical runtime is often much better.

Space

O(L + k), where L is the word length (for recursion) and k is the alphabet size (for frequency counts). Since k is constant, this simplifies to O(L).

Trade-offs

Pros

More efficient in practice by avoiding searches that are guaranteed to fail.
The pruning logic is relatively cheap to compute compared to the cost of the search itself.
Reduces the number of starting points for the DFS, which is a major performance bottleneck.

Cons

The added complexity of the pruning logic can make the code slightly harder to read and implement.
The effectiveness of the pruning depends on the specific board and word provided.

Solutions

Solution

1public class Solution {2    private int m;3    private int n;4    private char[][] board;5    private string word;6    public bool Exist(char[][] board, string word) {7        m = board.Length;8        n = board[0].Length;9        this.board = board;10        this.word = word;11        for (int i = 0; i < m; ++i) {12            for (int j = 0; j < n; ++j) {13                if (dfs(i, j, 0)) {14                    return true;15                }16            }17        }18        return false;19    }20    private bool dfs(int i, int j, int k) {21        if (k == word.Length - 1) {22            return board[i][j] == word[k];23        }24        if (board[i][j] != word[k]) {25            return false;26        }27        char c = board[i][j];28        board[i][j] = '0';29        int[] dirs = {30            -1,31            0,32            1,33            0,34            -135        };36        for (int u = 0; u < 4; ++u) {37            int x = i + dirs[u];38            int y = j + dirs[u + 1];39            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '0' && dfs(x, y, k + 1)) {40                return true;41            }42        }43        board[i][j] = c;44        return false;45    }46}

1class Solution {2private3  int m;4private5  int n;6private7  String word;8private9  char[][] board;10public11  boolean exist(char[][] board, String word) {12    m = board.length;13    n = board[0].length;14    this.word = word;15    this.board = board;16    for (int i = 0; i < m; ++i) {17      for (int j = 0; j < n; ++j) {18        if (dfs(i, j, 0)) {19          return true;20        }21      }22    }23    return false;24  }25private26  boolean dfs(int i, int j, int k) {27    if (k == word.length() - 1) {28      return board[i][j] == word.charAt(k);29    }30    if (board[i][j] != word.charAt(k)) {31      return false;32    }33    char c = board[i][j];34    board[i][j] = '0';35    int[] dirs = {-1, 0, 1, 0, -1};36    for (int u = 0; u < 4; ++u) {37      int x = i + dirs[u], y = j + dirs[u + 1];38      if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '0' &&39          dfs(x, y, k + 1)) {40        return true;41      }42    }43    board[i][j] = c;44    return false;45  }46}

1function exist ( board , word ) { const [ m , n ] = [ board . length , board [ 0 ]. length ]; const dirs = [ - 1 , 0 , 1 , 0 , - 1 ]; const dfs = ( i , j , k ) => { if ( k === word . length - 1 ) { return board [ i ][ j ] === word [ k ]; } if ( board [ i ][ j ] !== word [ k ]) { return false ; } const c = board [ i ][ j ]; board [ i ][ j ] = ' 0 ' ; for ( let u = 0 ; u < 4 ; ++ u ) { const [ x , y ] = [ i + dirs [ u ], j + dirs [ u + 1 ]]; const ok = x >= 0 && x < m && y >= 0 && y < n ; if ( ok && board [ x ][ y ] !== ' 0 ' && dfs ( x , y , k + 1 )) { return true ; } } board [ i ][ j ] = c ; return false ; }; for ( let i = 0 ; i < m ; ++ i ) { for ( let j = 0 ; j < n ; ++ j ) { if ( dfs ( i , j , 0 )) { return true ; } } } return false ; }

1class Solution {2public:3  bool exist(vector<vector<char>> &board, string word) {4    int m = board.size(), n = board[0].size();5    int dirs[5] = {-1, 0, 1, 0, -1};6    function<bool(int, int, int)> dfs = [&](int i, int j, int k) -> bool {7      if (k == word.size() - 1) {8        return board[i][j] == word[k];9      }10      if (board[i][j] != word[k]) {11        return false;12      }13      char c = board[i][j];14      board[i][j] = '0';15      for (int u = 0; u < 4; ++u) {16        int x = i + dirs[u], y = j + dirs[u + 1];17        if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '0' &&18            dfs(x, y, k + 1)) {19          return true;20        }21      }22      board[i][j] = c;23      return false;24    };25    for (int i = 0; i < m; ++i) {26      for (int j = 0; j < n; ++j) {27        if (dfs(i, j, 0)) {28          return true;29        }30      }31    }32    return false;33  }34};

1class Solution:2    def exist(self, board: List[List[str]], word: str) -> bool: def dfs(i, j, cur):  # cur: current char count if cur == len ( word ): return True if ( i < 0 or i >= m or j < 0 or j >= n or board [ i ][ j ] == '0' or word [ cur ] != board [ i ][ j ] ): return False t = board [ i ][ j ] board [ i ][ j ] = '0' # mark as visited for a , b in [[ 0 , 1 ], [ 0 , - 1 ], [ - 1 , 0 ], [ 1 , 0 ]]: x , y = i + a , j + b if dfs ( x , y , cur + 1 ): return True board [ i ][ j ] = t return False m , n = len ( board ), len ( board [ 0 ]) return any ( dfs ( i , j , 0 ) for i in range ( m ) for j in range ( n ))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem