Word Search II（c++单词搜索 II）

向右看齐 2022-09-02 04:16 200阅读 0赞

（1）回溯+前缀树

class Trie {
    public:
        vector<Trie*> v;
        bool isend;
    public:
        
        Trie():v(26),isend(false) {
        }
    
        void insert(string word) {
            Trie* node=this;
            for(int i=0;i<word.length();i++) {
                int index=word[i]-'a';
                if(node->v[index]==nullptr) {
                    node->v[index]=new Trie();
                }
                node=node->v[index];
            }
            node->isend=true;
        }
    };
     
    class Solution {
    private:
        vector<vector<int>> d={
       {0,1},{0,-1},{1,0},{-1,0}};
        int m,n;
    public:
        void helper(vector<vector<char>>& board, int x, int y, Trie* root, string word, set<string>& result){
            
            if(root->v[board[x][y]-'a'] != nullptr){
                word=word+board[x][y];
                root=root->v[board[x][y]-'a']; 
                if(root->isend) result.insert(word);
                char c=board[x][y];
                board[x][y]=' ';
                for(int i=0;i<d.size();i++) {
                    int x1=x+d[i][0];
                    int y1=y+d[i][1];
                    if(x1>=0 && x1<m && y1>=0 && y1<n && board[x1][y1]!=' ') {
                        helper(board, x1, y1, root, word, result);
                    }
                }
                board[x][y]=c;  
            }
            return;
        }
    
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            Trie* trie = new Trie();
            for(auto &&w:words) {
                trie->insert(w);
            }
            
            m=board.size(),n=board[0].size();
            set<string> result_set;
            for(int i=0; i<m; i++)
                for(int j=0; j<n; j++)
                    helper(board, i, j, trie, "", result_set);
            
            vector<string> result;
            for(auto it:result_set) result.push_back(it);
            return result;        
        }
    };