Word Search

Word search is something like the word-finding puzzles at some time in our life. Today I bring to the table a modified crossword.

My readers must be a bit perplexed as to what I am talking about. Without wasting any more time let us get to the problem statement

Can you find all the words?

We can construct the word from vertically or horizontally adjacent words. The catch is that you cannot use the same letter again.

Example

Let’s look at a few examples

Input : [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]]

Word : “ABCB”

Output: true

Input [[“A”,”B”,”C”,”E”],[“S”,””F”,”C”,”S”],[“A”,”D”,”E”,”E”]]

Word : “SEE”

Output: true

What can we do?

Here are some points which we follow to perform Word search in the puzzle.

• Loop through the matrix and start from the place where we find the first letter
• Let the current character be cur and check through the string recursively using DFS.
• If we reach the end of the word i.e we have found all the characters in the matrix we return true
• Check each character of the matrix
• If the character is in the word look into cells
  • Horizontally ahead
  • Horizontally behind
  • Vertically above
  • Vertically below
  • If any of the calls return true. Yay! we have found the word. We do not need to search for any longer
  • Return an OR from all the calls
• If the character is not found we return false 
• To ensure that we do not keep going back to the same cell we mask each cell’s value with a stray character

Let us understand it better with the help of a code snippet

Java Code For Word Search

class Solution
{
    boolean trav(char[][] board,int cur,int i,int j,String word)
    {
       //If we have found all the characters
       if(cur>=word.length())
            return true;
       //In case the character does not match/we go out of the board
       if(i<0 || j<0 || i>=board.length || j>=board[i].length || 
          board[i][j]!=word.charAt(cur))
            return false;
        //Masking our board to prevent repetitive calls
        char temp=board[i][j];
        board[i][j]='*';
        boolean ans=(trav(board,cur+1,i+1,j,word) || trav(board,cur+1,i,j+1,word)
                     || trav(board,cur+1,i-1,j,word) || trav(board,cur+1,i,j-1,word));
        board[i][j]=temp;
            return ans;   
    }
    public boolean exist(char[][] board, String word) 
    {
        boolean ans=false;
        for(int i=0;i<board.length;i++)
        {
            for(int j=0;j<board[i].length;j++)
            {
                //We start checking from where we find the first character
                if(board[i][j]==word.charAt(0) && trav(board,0,i,j,word))
                {
                    return true;
                }
            }
        }
        return false;
    }
}

C++ Code For Word Search

{
public:
    bool trav(vector<vector<char>>& board,int cur,int i,int j,string word)
    {
       if(cur>=word.length())
            return true;
       if(i<0 || j<0 || i>=board.size() || j>=board[i].size() || 
          board[i][j]!=word[cur])
            return false;
        char temp=board[i][j];
        board[i][j]='*';
        bool ans=(trav(board,cur+1,i+1,j,word) || trav(board,cur+1,i,j+1,word)
                     || trav(board,cur+1,i-1,j,word) || trav(board,cur+1,i,j-1,word));
        board[i][j]=temp;
            return ans;   
    }
public:
    bool exist(vector<vector<char>>& board, string word)
    {
     for(int i=0;i<board.size();i++)
     {
     for(int j=0;j<board[i].size();j++)
     {
     if(board[i][j]==word[0] && trav(board,0,i,j,word))
     {
     return true;
     }
     }
     }
    return false;   
    }
};

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

ABCB

true

Complexity Analysis

Time complexity:O(m*n*l)

Where,

m=Length of matrix

n=Width of matrix

l=Length of the word given in the word search problem.

How?

• We traverse through the entire board trying to find out the first letter of the word provided
  • In the worst case, we might traverse the entire board without hitting the first character
  • We then search the nearby characters until we hit on the next character
    • We thus traverse through the entire word
    • The time complexity of doing so=O(L)
  • This O(L) operation can be invoked every time in the outer loop of O(M). Making time complexity until now O(M*L)
• The above operations run in a loop of O(N)
• The three loops come together to make the time complexity=O(M*N*L)