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(); for(auto word:words) addword(word); } void addword(string &word){ 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(); } };
Leave a Comment