# My C++ solution based on trie (45ms)

• ``````struct node{
node* next[26];
char c;
bool isleaf;
bool found;
node():c('\0'), isleaf(false), found(false){
for(int i=0; i<26; ++i) next[i]=NULL;
}
node(char ch):c(ch), isleaf(false), found(false){
for(int i=0; i<26; ++i) next[i]=NULL;
}
};
class Trie{
public:
Trie(){
root = new node();
}
void insert(string word){
node* p = root;
for(int i=0; i<word.size(); ++i){
int idx = word[i]-'a';
if(!p->next[idx])
p->next[idx] = new node(word[i]);
p = p->next[idx];
}
p->isleaf = true;
}

node* root;
};
class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
trie = new Trie();
for(int i=0; i<words.size(); ++i) trie->insert(words[i]);
vector<string> res;
node* cur = trie->root;
int m=board.size(), n=board[0].size();
for(int i=0; i<m; ++i)
for(int j=0; j<n; ++j){
string tmp = "";
helper(board, res, tmp, i, j, cur);
}
return res;
}
private:
Trie* trie;
void helper(vector<vector<char>>& board, vector<string>& res, string& tmp, int i, int j, node* cur){
int m=board.size(), n=board[0].size();
if(i<0||i==m||j<0||j==n||board[i][j]=='\0') return;
int idx = board[i][j]-'a';
node* next = cur->next[idx];
if(!next) return;
if(next&&next->isleaf&&!next->found){
tmp.push_back(board[i][j]);
res.push_back(tmp);
next->found=true;
tmp.pop_back();
}
char ch = board[i][j];
board[i][j] = '\0';
tmp.push_back(ch);
helper(board, res, tmp, i-1, j, next);
helper(board, res, tmp, i, j-1, next);
helper(board, res, tmp, i+1, j, next);
helper(board, res, tmp, i, j+1, next);
tmp.pop_back();
board[i][j] = ch;
}
};
``````

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