Word Search 1 - Find if word exists

Problem

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

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

Follow ups

Follow up 1 - 8 direction search

What if all movements are allowed - right, left, up, down and diagonally. We cover the solution as a follow up: [#Follow up - 8 Direction Movement](#follow-up---8-direction-movement).

Example 1

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

Output: true

Follow up 2 - Return all words

[Word Search 2 - Return All Words](word-search-2-return-all-words)

Solution

Method 1 - Backtracking

This problem can be solve by using a typical DFS method and backtracking.

We need to make sure that we don't visit the same character again, if it is already used in word search. We can either use hashSet or we can modify the board temporarily. We will use some char like # OR * whenever we use some char in board, and revert after checking and backtrack.

Video explanation

Here is the video explaining this method in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/QlSnqWNE1tY" frameborder="0" allowfullscreen></iframe></div>

Code

Java

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        
        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 r, int c, int idx) {
        if (idx == word.length()) {
            return true; // All characters matched
        }
        
        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != word.charAt(idx)) {
            return false; // Out of bounds or character doesn't match
        }
        
        char temp = board[r][c];
        board[r][c] = '#'; // Mark as visited
        
        boolean ans = dfs(board, word, r - 1, c, idx + 1) ||   // up
                    dfs(board, word, r + 1, c, idx + 1) ||   // down
                    dfs(board, word, r, c - 1, idx + 1) ||   // left
                    dfs(board, word, r, c + 1, idx + 1);     // right
        
        board[r][c] = temp; // Unmark (restore original state)
        
        return ans;
    }
}

Python

 class Solution:
      def exist(self, board: List[List[str]], word: str) -> bool:
          m, n = len(board), len(board[0])
          
          def dfs(r: int, c: int, idx: int) -> bool:
              if idx == len(word): 
                  return True  # All characters matched
              
              if r < 0 or c < 0 or r >= m or c >= n or board[r][c] != word[idx]:
                  return False # Out of bounds or character mismatch
              
              temp = board[r][c]
              board[r][c] = '#'  # Mark visited
              
              ans = dfs(r - 1, c, idx + 1) or dfs(r + 1, c, idx + 1) or \
                    dfs(r, c - 1, idx + 1) or dfs(r, c + 1, idx + 1) 
              
              board[r][c] = temp  # Restore original state
              return ans
          
          for i in range(m):
              for j in range(n):
                  if dfs(i, j, 0):
                      return True
          
          return False

Complexity

• ⏰ Time complexity: O(m * n * 4^L), where L is the length of the word, and m x n are the grid dimensions. As we are finding the word of length L, the depth of the recursion is L. Each cell can produce up to 4 recursive calls (for adjacent directions), leading to 4^L calls per word. This process is repeated for every cell in the worst case, which adds the factor of m * n.
• 🧺 Space complexity: O(L), due to the recursion stack used in backtracking. The depth of recursion corresponds to the length of the word.