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.

Sample Test Cases

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.

Intuition

We need to recursively go through the grid starting from the first letter of the word we are searching for and then go in all 4 directions in search of the next characters. If the index reaches the end index of the word, then we have found the word; we can return true, else we still go on searching for the word until all the cells are visited.

Approach

• Traverse through the matrix and stop at the first character of the word.
• Perform recursion in all four directions, keeping in mind that we are not going out of bounds, revisiting a cell, or visiting a cell we are not interested in.
• Check all 4 direction cells and undo the visited operation. If we couldn't find the word in the current recursion, we might find it later.
• Return true if we went through all the characters of the word.

Complexity

• Time complexity:

  O(row * col * 4 ^ length of word)

• Space complexity:

  O(row * col) for boolean array

Code

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) {
            return false;
        }
        int row = board.length;
        int col = board[0].length;
        boolean [][] visited = new boolean [row][col];
        int movingIndex = 0;
        for (int currentRow = 0; currentRow < row; currentRow++) {
            for (int currentCol = 0; currentCol < col; currentCol++) {
                if (board[currentRow][currentCol] == word.charAt(0)) {
                    boolean isWordFound = findWord(board, currentRow, currentCol, 0, word, visited);
                    if (isWordFound) {
                        return true;
                    }
                }   
            }
        }
        return false;
    }

    private boolean findWord(char [][] board, int currentRow, int currentCol, int index, String word, boolean [][] visited) {
        if (index == word.length()) {
            return true;
        }
        if (currentRow < 0 || currentCol < 0 || currentRow >= board.length || currentCol >= board[0].length || visited[currentRow][currentCol] || board[currentRow][currentCol] != word.charAt(index)) {
            return false;
        }
        visited[currentRow][currentCol] = true;
        boolean isPossible = findWord(board, currentRow + 1, currentCol, index + 1, word, visited) || 
        findWord(board, currentRow - 1, currentCol, index + 1, word, visited) || 
        findWord(board, currentRow, currentCol + 1, index + 1, word, visited) || 
        findWord(board, currentRow, currentCol - 1, index + 1, word, visited);
        visited[currentRow][currentCol] = false;
        return isPossible;
    }
}