Home » Technical Interview Questions » Matrix Interview Questions » Word Search

# 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 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
• To ensure that we do not keep going back to the same cell we mask each cell’s value with a stray character
READ  K-th Smallest Element in a Sorted Matrix

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 && 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)
 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions 