Word Search medium

Problem Statement

Given an m x n board and a word word, find 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: 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

Steps

  1. Depth-First Search (DFS): We'll use DFS to explore the board. DFS is ideal for traversing connected components like the paths in this grid.

  2. Base Cases:

    • If the word is empty, return true (we've found it!).
    • If we're out of bounds, or the current cell doesn't match the expected letter, return false.

  3. Recursive Step:

    • Mark the current cell as visited (to avoid cycles).
    • Recursively explore the four adjacent cells (up, down, left, right).
    • If any recursive call returns true, the word exists, so return true.
    • Backtrack: Unmark the current cell as visited (crucial to explore other paths). Return false if none of the recursive calls found the word.

  4. Iteration: Iterate through each cell in the board as a starting point for the DFS.

Explanation

The solution efficiently searches for the word using DFS. The backtracking step is critical to allow exploration of multiple paths. By marking cells as visited, we prevent revisiting the same cell within a single path, ensuring that each letter is used only once in a given path. If the word is not found starting from any cell, the function returns false.

Code

class Solution {
    private int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // Right, Left, Down, Up
    private int rows, cols;
    private boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        rows = board.length;
        cols = board[0].length;
        visited = new boolean[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(board, word, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

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

        if (row < 0 || row >= rows || col < 0 || col >= cols || visited[row][col] || board[row][col] != word.charAt(index)) {
            return false; // Out of bounds, visited, or letter mismatch
        }

        visited[row][col] = true; // Mark as visited

        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            if (dfs(board, word, index + 1, newRow, newCol)) {
                return true; // Word found in recursive call
            }
        }

        visited[row][col] = false; // Backtrack: Unmark as visited
        return false; // Word not found from this path
    }
}

Complexity

  • Time Complexity: O(M * N * 4L), where M and N are the dimensions of the board, and L is the length of the word. In the worst case, we might explore all possible paths for each cell.
  • Space Complexity: O(M * N) for the visited matrix, plus O(L) for the recursion stack in the DFS. Therefore, the space complexity is dominated by the visited matrix, making it O(M * N).