# Word Search II

Problem statement: Given an m*n “board” of characters and a list of strings “words”, return all the words present on the board. Each word that you look up on the board must be constructed from adjacent letters( vertical or horizontal neighboring cells), sequentially such that no letter is used more than once in a word.

Note: Both the ‘board’ and the strings in ‘words’ contain lowercase alphabets only.

Examples:

`Input:`
```words={“mom”,” elephant”,” bob”,” badam”,” glad”}

Explanation: In the grid, you are able to find the

### Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Intuition: Whenever an array of strings, here it is ‘words’, is given, and then you are expected to find all possible words in a grid or if you are given any other similar kind of situation wherein a dictionary is involved, then it means you have to use trie data structure. This will be even more clear if you watch the 7 video lectures of the trie playlist by striver.

Approach:

The approach is very straightforward. After getting familiarized with trie data structure after you watch the above playlist, you will find implementing a trie, a very easy task. Hence let’s discuss the extra logic that comes into the picture here.

After you insert all the words into the trie, start doing a DFS at each position in the grid, standing at the root of the trie. At each step, check whether there exists a node attached to the alphabet corresponding to the one present in the grid. If yes, proceed to that particular node and in the grid, go to that particular alphabet cell. At each step, check whether the flag of that node is set to true or not. If it is true, then you know that you have reached the end of that particular word of the ‘words’ array. String ‘s’ will keep track of this string and it will be inserted into your ‘ans’ array. Array simply refers to vector, the dynamic array in C++.

This solution also employs a backtracking technique because you make a cell ‘*’ once you go to that so that the same character doesn’t repeat in the same word again and this change has to be reverted back once we have checked for that word so that you are not missing out on finding other words that are possibly associated with these changed characters. Also, it is not a good practice to modify the given input array when it’s passed by address.

Here,

• search() of trie does DFS search.
• insert(word) of trie inserts word into the trie.
• put(ch, temp) will link the ch of the ‘links’ array to a new node temp.
• containsKey(ch) tells whether there is a node associated with that ch in that node or not.
• get(ch) will return the node linked to ch.
• findWords() our leetcode function will call the search function of trie to make a DFS in that particular cell.

Code:

## C++ Code

``````struct Node{
bool flag=false;
Node* get(char ch){
}
void put(char ch,Node* temp){
}
bool containsKey(char ch){
}
};

class Trie{
public: Node* root;
Trie(){
root=new Node();
}

void insert(string s){
Node* temp=root;
for(int i=0;i<s.length();i++){
if(!temp->containsKey(s[i]))
temp->put(s[i],new Node());
temp=temp->get(s[i]);
}
temp->flag=true;
}

void search(vector<vector<char>> &board, Node* temp,int i,int j,vector<string>
&ans,string s){
//temp is the current node in the trie.
// (i,j) is the current cell in the grid.
if(i<0 || j<0 || i==board.size() || j==board.size() || !temp ||
board[i][j]=='*' || !temp->containsKey(board[i][j])) return;
s+=board[i][j];
Node* t=temp->get(board[i][j]);
if(t->flag){
ans.push_back(s);
t->flag=false;
}
char ch=board[i][j];
board[i][j] = '*'; //preventing this from getting reconsidered in same word
search(board,temp->get(ch),i+1,j,ans,s); //bottom cell
search(board,temp->get(ch),i,j+1,ans,s); //right cell
search(board,temp->get(ch),i-1,j,ans,s); // top cell
search(board,temp->get(ch),i,j-1,ans,s); //left cell
board[i][j]=ch; //restoring original character
}
};

class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
Trie trie;
for(string s:words) trie.insert(s);
vector<string> ans;
for(int i=0;i<board.size();i++)
for(int j=0;j<board.size();j++)
trie.search(board,trie.root,i,j,ans,"");
return ans;
}
};
``````

Time complexity: O(m*n*max(length of a word in the array ‘words’)), m*n because DFS calls are made for every cell in search of a word, and max(length of a word in the array ‘words’) means that these many recursive calls can be made at max.

Space complexity: O(max(length of word in the array ‘words’) * size of the ‘words’ array), Reason is, that we can’t consider ans array in this calculation as it is a necessity of the problem and that the recursive stack space used in the search() is, max(length of a word in the array ‘words’), which is relatively smaller to this. So the trie data structure can consume the largest space in the worst case.