Word Search Leetcode Solution

Problem Statement

Given an m x n board and a 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 neighbouring. 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"]],

word = "ABCCED"

true

Explanation:

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

word = "ABCB"

false

Approach ( Backtracking )

This is a 2D grid traversal problem, where we have to explore the grid to check if the given word can be formed using adjacent cells of the grid. But instead of performing DFS on whole grid space we would more optimally use backtracking method. In backtracking method we will only go to that path to find the solution which matches our aim. If we know at some point that the current path will not lead to the solution then we will backtrack and go for the next choice.

We will go around the grid by marking the current cell in our path as visited at each step. And at end of each step we will also unmark it so that we could have a clean state to try another direction.

Algorithm

We would make a backtracking function which will start with a particular cell and traverse the adjacent cells of grid in DFS fashion. Because the given word can start from anywhere in the grid, we would loop over all the cells of the grid and for each cell we will call the backtracking function starting from this current cell.
As this backtracking function is a recursive function, below are the steps to implement this recursive function:

1. In the beginning we will check if we have reached to the bottom or the base case of the recursion. If the word to be searched is empty or in other words if it’s found, we return true.
2. We check if our path is currently valid or not by checking if we have crossed the boundary of the grid or if the current cell matches the first character of the search word or not.
3. If the current step is valid then mark this cell as visited. And start exploring the four directions by calling the same backtracking function for right, down, left and up cells.
4. At end we un-visit the current cell and return the result of exploration as true or false. If any of the sub exploration results in true then we return true from here otherwise return false.

Implementation

C++ Program for Word Search Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

int row,col;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

bool backtrack(int i,int j,vector<vector<char>>& board, string word,unsigned int ind)
{
    if(ind>=word.size()) return true;
    if(i<0 || i>=row || j<0 || j>=col || board[i][j]!=word[ind]) return false;

    char t=board[i][j];
    board[i][j]= '#';

    for(int k=0;k<4;k++)
    {
        if(backtrack(i+dx[k],j+dy[k],board,word,ind+1))
            return true;
    }
     board[i][j] = t;
    return false;

}

bool exist(vector<vector<char>>& board, string word) 
{
    row= board.size();
    col= board[0].size();

    for(int i=0;i<row;i++)
        for(int j=0;j<col;j++)
            if(backtrack(i,j,board,word,0))
                return true;
    return false;
}

int main() 
{
     vector<vector<char>> board= {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        };
    string word = "ABCCED";
    if(exist(board,word))
        cout<< "true" ;
    else
        cout<< "false" ;
    return 0; 
}

true

Java Program for Word Search Leetcode Solution

class Rextester{
    
  static int row,col;
    static int dx[] = {0, 1, 0, -1};
    static int dy[] = {1, 0, -1, 0};
    
    public static boolean exist(char[][] board, String word)
    {
        row= board.length;
        col= board[0].length;
        
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
                if(backtrack(i,j,board,word,0))
                    return true;
        
        return false;       
    }
    
    static boolean backtrack(int i,int j,char[][] board, String word,int ind)
    {
        if(ind>=word.length()) return true;
        if(i<0 || i>=row || j<0 || j>=col || board[i][j]!=word.charAt(ind)) return false;
        
        char t=board[i][j];
        board[i][j]= '#';
        
        for(int k=0;k<4;k++)
        {
            if(backtrack(i+dx[k],j+dy[k],board,word,ind+1))
                return true;
        }
        
        board[i][j] = t;
        return false;        
    }
    
  public static void main(String args[])
    {
        char[][] board= {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        };
        String word = "ABCCED";
    System.out.println(exist(board,word));
    }
}

true

Complexity Analysis for Word Search Leetcode Solution

Time Complexity

O( N*(3^L) ) : where N is the total number of cells in the grid and L is the length of the given word to be searched. For the backtracking function initially we get 4 choices for directions but further it reduced to 3 as we have already visited it in previous step. This depth of the this recursive function will be equal to the length of the word (L). Hence in worst case total number of function invocation will be the number of nodes in 3-nary tree, which is about 3^L.
In worst case we call this function starting from N number of cells. Hence overall time complexity will be O( N*(3^L) ).

Space Complexity 

O(L) : where L is the length of the given word. This space is used for recursion stack.