# A detailed explanation C++ solution (Trie + backtracking)

• ``````class Solution {
public:

//
// The Trie Node structure
//

struct TrieNode
{
TrieNode *Nodes[26];
string Word;

TrieNode()
{
memset(&Nodes,0,sizeof(Nodes));
}
} *Root;

//
// Adds a word to the Trie by iteratively looking
// at each character of the word and creating a new Node
// for it, if it doesn't exist
//
{
TrieNode *Curr = Root;

for(auto &c : str)
{
if(Curr->Nodes[c - 'a'] == NULL)
{
Curr->Nodes[c - 'a'] = new TrieNode;
}

Curr = Curr->Nodes[c - 'a'];
}

Curr->Word = str;
}

Solution()
:
Root(new TrieNode)
{
}

//
// This is the DFS main function
//

void Visit(vector<vector<char>>& board,int i, int j, TrieNode *R, unordered_set<int> &Visited,unordered_set<string> &Res)
{
static vector<pair<int,int>> Dir = {{-1,0},{1,0},{0,-1},{0,1}};

//
// If the TrieNode is NULL bail out
//
if(R == NULL)
{
return;
}

//
// if we reached a leaf node of the trie,
// add the word to the Res set but continue
// looking as there might be more words that have this current
// word as a prefix.
//

if(R->Word.empty() == false)
{
Res.insert(R->Word);
R->Word.clear();
}

//
// check all 4 directions of this current board location
// if they are in bound and we have not visited them during this
// current traversal (we don't want loops) add them to the visited
// set and recusively visit them.
// when we return from the recursion we need to remove them from the
// visited set so that they may be traversed from a different path.
//

for(auto &P : Dir)
{
int Ni = i + P.first;
int Nj = j + P.second;

if(Ni >= 0 && Ni < board.size() && Nj >= 0 && Nj < board[Ni].size())
{
int V = Ni*(board[Ni].size()) + Nj;

if(Visited.find(V) == Visited.end())
{
Visited.insert(V);
Visit(board,Ni,Nj,R->Nodes[board[Ni][Nj] - 'a'],Visited,Res);
Visited.erase(V);
}
}
}
}

vector<string> findWords(vector<vector<char>>& board, vector<string>& words)
{
//
// Add the words from the dictionary to the Trie
//
for(auto &s : words)
{
}

//
// We'll store the words we locate in a set
// so that we will avoid duplicates
//

unordered_set<string> Res;

for(int i = 0; i < board.size(); ++i)
{
for(int j = 0; j < board[0].size(); ++j)
{
unordered_set<int> Visited;
Visited.insert(i*board[0].size() + j);
Visit(board,i,j,Root->Nodes[board[i][j] - 'a'],Visited,Res);
}
}

return (vector<string>(Res.begin(),Res.end()));
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.