# Word Search  Difficulty Level Medium
Frequently asked in Amazon Apple Bloomberg ByteDance Cisco Facebook Intuit Microsoft Oracle ServiceNow Snapchat
Array Backtracking

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
N queen problem

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?