https://leetcode.com/problems/word-search-ii/
I am preparing for my interviews and I am trying out this problem. My approach is based on backtracking and I use Tries to check if a prefix of the current string in the recursion exists in the trie. If a prefix does not exist, then return control back.
This approach passes 32/36 test cases.
How do I optimize this further to pass all 36 TCs ?
Please have a look at my code.
struct Trie
{
bool is_leaf;
unordered_map<char,Trie*>children;
Trie(bool il)
{
is_leaf=il;
}
bool search(string s)
{
int i=0;
int n=s.length();
Trie *cur=this;
while(i<n)
{
if(cur->children[s[i]]!=NULL)
{
cout<<s[i];
cur=cur->children[s[i]];
i++;
}
else
{
return false;
}
}
if(cur->is_leaf)
return true;
return false;
}
bool find_prefix(string s)
{
int i=0;
int n=s.length();
Trie *cur=this;
while(i<n)
{
if(cur->children[s[i]]!=NULL)
{
cout<<s[i];
cur=cur->children[s[i]];
i++;
}
else
{
return false;
}
}
return true;
}
void add_str(string s)
{
int i=0;
int n=s.length();
cout<<n<<endl;
Trie *cur=this;
while(i<n)
{
if(cur->children[s[i]]!=NULL)
{
cout<<s[i]<<endl;
cur=cur->children[s[i]];
i++;
}
else
{
break;
}
}
if(i==n)
return;
cur->is_leaf=false;
cur->children[s[i]]=new Trie(1);
cur=cur->children[s[i]];
i++;
while(i<n)
{
cur->is_leaf=false;
cur->children[s[i]]=new Trie(1);
cur=cur->children[s[i]];
i++;
}
cur->is_leaf=true;
}
};
class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
Trie* t=new Trie(0);
for(int i=0;i<26;i++)
{
t->children['A'+i]=new Trie(1);
t->children['a'+i]=new Trie(1);
}
for(int i=0;i<=9;i++)
{
t->children['0'+i]=new Trie(1);
}
set<string>found;
unordered_map<string,bool>con;
vector<vector<bool> >visited(board.size());
for(int i=0;i<board.size();i++)
{
vector<bool>row(board[0].size(),0);
visited[i]=row;
}
for(auto it=words.begin();it!=words.end();it++)
{
con[*it]=true;
t->add_str(*it);
}
for(int i=0;i<board.size();i++)
{
for(int j=0;j<board[0].size();j++)
{
string s="";
if(!visited[i][j])
{
visited[i][j]=true;
s.push_back(board[i][j]);
findUtil(board,words,i,j,found,s,con,visited,t);
s.pop_back();
visited[i][j]=false;
}
}
}
vector<string>ans;
for(auto it=found.begin();it!=found.end();it++)
ans.push_back(*it);
return ans;
}
void findUtil(vector<vector<char>>& board, vector<string>&words,int i,int j,set<string>&found,string s,unordered_map<string,bool>con,vector<vector<bool> >&visited,Trie* t)
{
if(con[s])
{
found.insert(s);
cout<<s<<endl;
//cout<<i<<" "<<j<<endl;
}
cout<<i<<" "<<j<<endl;
if(i-1>=0 && i<board.size() && j>=0 && j<board[0].size() && !visited[i-1][j] && t->find_prefix(s))
{
visited[i-1][j]=true;
s.push_back(board[i-1][j]);
findUtil(board,words,i-1,j,found,s,con,visited,t);
s.pop_back();
visited[i-1][j]=false;
}
if(i>=0 && i<board.size() && j-1>=0 && j<board[0].size() && !visited[i][j-1] && t->find_prefix(s))
{
visited[i][j-1]=true;
s.push_back(board[i][j-1]);
findUtil(board,words,i,j-1,found,s,con,visited,t);
s.pop_back();
visited[i][j-1]=false;
}
if(i>=0 && i+1<board.size() && j>=0 && j<board[0].size() && !visited[i+1][j] && t->find_prefix(s))
{
visited[i+1][j]=true;
s.push_back(board[i+1][j]);
findUtil(board,words,i+1,j,found,s,con,visited,t);
s.pop_back();
visited[i+1][j]=false;
}
if(i>=0 && i<board.size() && j>=0 && j+1<board[0].size() && !visited[i][j+1] && t->find_prefix(s))
{
visited[i][j+1]=true;
s.push_back(board[i][j+1]);
findUtil(board,words,i,j+1,found,s,con,visited,t);
s.pop_back();
visited[i][j+1]=false;
}
}
};