Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
[code lang="java"]
class Solution {
    public boolean exist(char[][] board, String word) {

    }
}
[code]

Idea – 1

We do dfs once from every cell of the board. A cell would stay ‘visited’ only for the fours sub-dfses from its four neighbors, otherwise we remove the cell from ‘visited’ list, this is to allow some other path to use this cell. Consider below, during dfs from cell x, we first visit its right neighbor cell y. All 4 neighbors of cell y fail to find a match, do we now keep cell y marked as ‘visited’?
No. Because there could be a legitimate path from x through x’s bottom neighbor and that path may require cell y like below:
Since the graph has 4\cdot n edges, we ignore edge count in the complexity. We are doing n dfs’es, time complexity is O(n^2) and since we are doing a single dfs any one time space complexity is O(n). 
[code lang="java"]
class Solution {
    public boolean exist(char[][] board, String word) {
        if(board==null)
        {
            return false;
        }
        
        if(board.length==0)
        {
            return word.isEmpty();
        }
        
        int m = board.length;
        int n = board[0].length;
        
        for(int row = 0; row < m; ++row)
        {
            for(int col = 0; col < n; ++col)
            {
                if(dfs(board, row, col, word, 0))
                {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean dfs(char[][] board, int row, int col, String word, int i)
    {
        if(i >= word.length())
        {
            return true;
        }
        
        int m = board.length;
        int n = board[0].length;
        
        if(row < 0 || row >= m || col < 0 || col >= n || board[row][col] == '*' || word.charAt(i) != board[row][col])
        {
            return false;
        }
        
        char old = board[row][col];
        board[row][col] = '*';
        
        boolean found = 
               dfs(board, row-1, col, word, i+1) 
            || dfs(board, row, col+1, word, i+1) 
            || dfs(board, row+1, col, word, i+1) 
            || dfs(board, row, col-1, word, i+1);
        
        board[row][col] = old;
        
        return found;
    }
}
[code]

Runtime: 4 ms, faster than 93.95% of Java online submissions for Word Search.Memory Usage: 37.4 MB, less than 96.83% of Java online submissions for Word Search.

Leave a comment