C++ solution using Trie


  • 0
    K
    class Solution {
        class TrieNode
            {
            public:
                TrieNode* children[26];
                string word;
                TrieNode()
                {
                    memset(children,0,sizeof(children));
                    word="";
                }
                ~TrieNode()
                {
                    for(auto p:children)
                        delete p;
                }
            };
    public:
        void buildTrie(TrieNode* root,vector<string>& words)
        {
            for(string word:words)
            {
                TrieNode* p=root;
                for(char c:word)
                {
                    if(p->children[c-'a']==NULL)
                        p->children[c-'a']=new TrieNode();
                    p=p->children[c-'a'];
                }
                p->word=word;
            }
        }
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            vector<string> res;
            if(board.empty()) return res;
            TrieNode* root=new TrieNode();
            buildTrie(root,words);
            for(int i=0;i<board.size();++i)
                for(int j=0;j<board[0].size();++j)
                    dfs(board,i,j,res,root);
            return res;
        }
        void dfs(vector<vector<char>>& board,int i,int j,vector<string>& res,TrieNode* p)
        {
            if(board[i][j]=='#'||p->children[board[i][j]-'a']==NULL) return;
            p=p->children[board[i][j]-'a'];
            if(p->word!="")
            {
                res.push_back(p->word);
                p->word="";
            }
            char c=board[i][j];
            board[i][j]='#';
            if(i>0) dfs(board,i-1,j,res,p);
            if(j>0) dfs(board,i,j-1,res,p);
            if(i<board.size()-1) dfs(board,i+1,j,res,p);
            if(j<board[0].size()-1) dfs(board,i,j+1,res,p);
            board[i][j]=c;
        }
    };

Log in to reply
 

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