# 128 ms DFS + Trie Simple C++ Solution

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

struct TrieNode{

bool is_end;
bool starts_with;
struct TrieNode* children[26];

};

struct TrieNode* createNode(){

struct TrieNode* n = new TrieNode;
n->is_end = false;
n->starts_with = false;

for(int i = 0 ; i < 26; i++){
n->children[i] = NULL;
}

return n;

}

void insert(TrieNode* root, string s){

int len = s.length();

for(int i = 0; i < len; i++){

if(root->children[s[i] - 'a'] == NULL){
root->children[s[i] - 'a'] = createNode();
root->children[s[i] - 'a']->starts_with = true;
}

root = root->children[s[i] - 'a'];
}

root->is_end = true;

}

bool search(TrieNode* root, string s){

int len = s.length();

for(int i = 0 ; i < len; i++){

if(root->children[s[i] - 'a'] == NULL){
return false;
}

root = root->children[s[i] - 'a'];
}

return root->is_end;
}

bool startsWith(TrieNode* root, string s){

int len = s.length();

for(int i = 0; i < len; i++){
if(root->children[s[i] - 'a']  == NULL){
return false;
}

root = root->children[s[i] - 'a'];
}

return root->starts_with;

}

void helper(vector<vector<char> >& board, string s, int x, int y, vector<string>& res, bool** track, TrieNode* root){

if(x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || track[x][y] == true){

return;
}

s += board[x][y];

if(!startsWith(root,s)){
return;
}

if(search(root,s)){

res.push_back(s);

}

track[x][y] = true;

helper(board, s,x-1,y,res,track,root);
helper(board, s,x+1,y,res,track,root);
helper(board, s,x,y-1,res,track,root);
helper(board, s,x,y+1,res,track,root);

track[x][y] = false;

}

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {

int n = words.size();
vector<string> res;
bool** track = new bool*[board.size()];

for(int i = 0 ; i < board.size(); i++){

track[i] = new bool[board[0].size()];
}

for(int i = 0;  i <  board.size(); i++){
for(int j = 0 ; j < board[0].size(); j++){
track[i][j] = false;
}
}

if(n == 0){

return res;
}

TrieNode* root = createNode();
for(int i = 0; i < n; i++){

insert(root,words[i]);

}

for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
helper(board,"",i,j,res,track,root);
}
}

sort(res.begin(),res.end());
res.erase( unique( res.begin(), res.end() ), res.end() );

return res;

}
};``````

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