Word Search Cont…

Question: 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.

You may view the full question here.

Approach 2: Before we dive in, let’s quickly list out the key Take-away from the previous approach —

• The checks were being made in a breadth first approach — we only checked if the character in the current position of the board matches with corresponding character in the search word. Instead, we should have checked in a depth first manner, if the full word could be found passing through this current character or not.
• Since, we are NOT trying to find all possible occurrences of the search word, the performance of the solution to find the first occurrence can be significantly improved by using depth first search.
• Next, we invested a lot of resources(time mainly) in making copies of the board.

Thanks to this brilliant post, here is a solution based on this DFS approach —

//Approach 2:
//Runtime: 3ms
//Memory usage: 40.1MB
class Solution {
    
    public boolean exist(char[][] board, String word) {
        char[] chars = word.toCharArray();
        for(int r = 0; r<board.length; r++){
            for(int c = 0; c<board[0].length; c++){
                if(check(board, chars, r, c, 0)){
                    return true;
                }
            }
        }
        return false;
    }
    
   private boolean check(char[][] board, char[] word, int currR, int currC, int currW){
       if(currR<0 || currR >= board.length || currC<0 || currC>=board[0].length){
           return false;
       }
       
       if(word[currW]==board[currR][currC]){
           char originalChar = board[currR][currC];
           //Mark as convered
           board[currR][currC] = '*';
           if(currW==word.length-1){
               return true;
           } else 
               //Proceed to check for the rest of the search word
               if(check(board, word, currR-1, currC, currW+1) //Top
           || check(board, word, currR+1, currC, currW+1) //Bottom
           || check(board, word, currR, currC-1, currW+1) //Left
           || check(board, word, currR, currC+1, currW+1) //Right
           ) {
               return true;
           }
           //Failed to find word 
           //passing through this matched character.
           //Therefore, Unmark
           board[currR][currC] = originalChar;
       }
       return false;
   }
}

Find more posts here.

Cheers & Chao!