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;
        }
            
    }
    
    
};