# c++ Trie solution with simple explanation.

• ``````class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> ans;
unordered_set<string> res;

r = board.size();
if(r <= 0)  return ans;
c = board[0].size();
if(c <= 0)  return ans;

trie = new TrieNode();
for(string word : words){
createTrie(word);
}

vector<vector<bool>> visited(r, vector<bool>(c,false));

for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
dfs(board, res, visited, i, j, "");
}
}

for(string word : res){
ans.push_back(word);
}
return ans;

}

void dfs(vector<vector<char>>& board, unordered_set<string>& res,vector<vector<bool>>& visited, int i, int j, string str){
if(i >= board.size() || i < 0 || j >=board[0].size() || j < 0 || visited[i][j])
return ;

str += board[i][j];

int state = find(str);
if (state == 1)  res.insert(str);
if (state == -1)  return;

visited[i][j] = true;
dfs(board, res, visited, i-1, j, str);
dfs(board, res, visited, i+1, j, str);
dfs(board, res, visited, i, j+1, str);
dfs(board, res, visited, i, j-1, str);
visited[i][j] = false;
}
private:
static const int MAX = 26;
struct TrieNode{
TrieNode* next[MAX];
bool isEnd;
TrieNode() {
isEnd = false;
for(int i = 0; i < 26; i++)
next[i] = nullptr;
}
};

TrieNode* trie;

int r;
int c;

void createTrie(string &str){
const int len = str.length();
TrieNode *p = trie, *q;
for(int i = 0; i < len; i++){
int id = str[i]-'a';
if(p->next[id] == nullptr){
q = new TrieNode();
if(i == len-1)  q->isEnd = true;
p->next[id] = q;
p = q;
}
else{
p = p->next[id];
}
}
p->isEnd = true;

}
int find(const string &str){ // 0 exists but not exactly is, 1 exactly is, -1 not exist at all
int len = str.length();
TrieNode* p = trie;
bool exist = false;
for(int i = 0; i < len; i++){
int id = str[i]-'a';
p = p->next[id];
if(!p){
return -1;
}
exist = true;
}
return p->isEnd ? 1 : 0;
}
};
``````

The idea is that we create a trie using the word in vector words. When we dfs the solution, given that the current word we get from the board, str , is included in trie, we go forward, else we return and try another path.

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