Leetcode 79 Word Search

Leetcode 79 Word Search

Edit Word Search on GitHub

The problem description is as follow:

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.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

This problem is a DFS problem. We could do a recursive Depth First Search function to solve it.

 public class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;  
        int n = board[0].length;  
        boolean[][] recordVisited = new boolean[m][n];  
          for (int i = 0; i < m; i++) {  
              for (int j = 0; j < n; j++) {  
                  if (wordSearch(board,recordVisited, word, 0, i, j))  
                      return true;  
              }  
         }  
         return false;  
    }
    
    public boolean wordSearch(char[][] board, 
                              boolean[][] recordVisited, 
                              String word, 
                              int visitedLength, 
                              int rowIndex, 
                              int colIndex) 
    {  
         if (visitedLength == word.length())  
             return true;  
         if (rowIndex<0 || colIndex<0 || rowIndex>=board.length || colIndex>=board[0].length)  
             return false;  
         if (recordVisited[rowIndex][colIndex])  
             return false;  
         if (board[rowIndex][colIndex] != word.charAt(visitedLength))  
             return false;  
         recordVisited[rowIndex][colIndex] = true;  
         boolean res = wordSearch(board,recordVisited,word,visitedLength+1,rowIndex-1,colIndex)  
                    || wordSearch(board,recordVisited,word,visitedLength+1,rowIndex+1,colIndex)  
                    || wordSearch(board,recordVisited,word,visitedLength+1,rowIndex,colIndex+1)  
                    || wordSearch(board,recordVisited,word,visitedLength+1,rowIndex,colIndex-1);  
         recordVisited[rowIndex][colIndex] = false;  
         return res;  
    }
}

Explanation

It’s pretty straightforward. We traverse every node in board as start node. For each iteration, we call the DFS function:

wordSearch(char[][] board, 
           boolean[][] recordVisited, 
           String word, 
           int visitedLength, 
           int rowIndex, 
           int colIndex)

– boolean[][] recordVisited is the boolean matrix to record a node in char[][] board is visited or not.

– int visitedLength is the length of the characters that is already visited.

– int rowIndex is the row index of the character we are looking into in char[][] board

– int colIndex is the column index of the character we are looking into in char[][] board

Then we do the following:

1. If the length of characters that is already visited == the length of word, it means the search succeed, word found.
2. If the row index or column index of the current character is out of the range of board, it means current search path fails, we should return to the previous character and search again.
3. If the current character is not the next character of word we are looking for, it means current search path fails.
4. Else, we it means the current search path can proceed, we should search for next character to see if it match. Since there are 4 directions (up, down, left and right), we have to call 4 DFS functions.

The most important tip is too set the node in board as not visited for other search path every time you finish the current search path:

recordVisited[rowIndex][colIndex] = false;