# Untitled

unknown
plain_text
13 days ago
1.9 kB
2
Indexable
Never
```class trienode{
public:
vector<trienode*> child;
bool is_word;
trienode(){
is_word=false;
child=vector<trienode*> (26,NULL);
}
};

class trie{
public:
trienode* root;

trienode* getroot(){ return root;}
trie(vector<string>&words){
root = new trienode();
}

int k=0;
trienode* cur=root;
for(auto i:word){
int k=i-'a';
if(!cur->child[k]) cur->child[k]=new trienode();
cur=cur->child[k];
}
cur->is_word=true;
}
};

class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
trie* mt =new trie(words);
trienode* root = mt->getroot();
set<string> res;
vector<vector<bool>> vis(board.size(),vector<bool>(board[0].size(),false));
for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
string path="";
dfs(board,i,j,root,path,res,vis);
}
}
vector<string> ans;
for(auto i:res) ans.push_back(i);
return ans;
}

void dfs(vector<vector<char>>& board,int x,int y,trienode* root,string path,set<string>&res,vector<vector<bool>> &vis){
if(x<0||x>=board.size()||y<0||y>=board[0].size()|| vis[x][y] || !root->child[board[x][y]-'a']) return;

vis[x][y]=1;
path+=board[x][y];
root = root->child[board[x][y]-'a'];
if(root->is_word) {
res.insert(path);
root->is_word=false;
}
dfs(board,x+1,y,root,path,res,vis);
dfs(board,x,y+1,root,path,res,vis);
dfs(board,x-1,y,root,path,res,vis);
dfs(board,x,y-1,root,path,res,vis);
vis[x][y]=0;
//path.pop_back();
}
};```