Multiple Word Searching Algorithm
In this article we are going to write the function that helps in find all the words present in a given2-D matrix.
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Example:
Input:
board = [
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
words =["oath","pea","eat","rain"]
Output:["eat","oath"]
Note:
- All inputs are consist of lowercase letters
a-z. - The values of
wordsare distinct.
We are only concerned about the function inside the solution class. Other functions are for pre-processing the inputs to handle all cases.
class Solution {
public:
string myword;
int row,col;
vector<vector<char>>bv;
bool vis[201][201]={false};
bool findword(int rw,int cl,int ind)
{
int sz=ind,slen=myword.length();
if(rw>=row||cl>=col)return false;
if(sz==slen)return true;
bool flag1=false,flag2=false,flag3=false,flag4=false,flag5=false;
if(sz==0){
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++){
if(bv[i][j]==myword[0]){
vis[i][j]=true;
flag1=findword(i,j,ind+1);
vis[i][j]=false;
if(flag1)return true;
}
}
}
}
int curcl,currw,prcl,prrw;
curcl=(cl+1);
currw=(rw+1);
prcl=cl-1;
prrw=rw-1;
// cout<<"cur row "<<currw<<" cur col "<<curcl<<" prev row "<<prrw<<" prev col "<<prcl<<endl;
if(curcl<col&&bv[rw][curcl]==myword[ind]&& vis[rw][curcl]==false){
// cout<<"if 1"<<endl;
vis[rw][curcl]=true;
flag2=findword(rw,curcl,ind+1);
vis[rw][curcl]=false;
if(flag2)return true;
}
if(prcl>=0&&bv[rw][prcl]==myword[ind]&&vis[rw][prcl]==false){
// cout<<"if 2"<<endl;
vis[rw][prcl]=true;
flag3=findword(rw,prcl,ind+1);
vis[rw][prcl]=false;
if(flag3)return true;
}
if(currw<row&&bv[currw][cl]==myword[ind]&&vis[currw][cl]==false){
// cout<<"if 3"<<endl;
vis[currw][cl]=true;
flag4=findword(currw,cl,ind+1);
vis[currw][cl]=false;
if(flag4)return true;
}
if(prrw>=0&&bv[prrw][cl]==myword[ind]&&vis[prrw][cl]==false){
// cout<<"if 4"<<endl;
vis[prrw][cl]=true;
flag5=findword(prrw,cl,ind+1);
vis[prrw][cl]=false;
if(flag5)return true;
}
return false;
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string>v=words;
row=board.size();
col=board[0].size();
bv=board;
vector<string>rv;
for(auto it:v){
myword=it;
bool flag=findword(0,0,0);
if(flag)rv.push_back(it);
}
return rv;
}
};
Comments