128 ms DFS + Trie Simple C++ Solution


  • 0
    B
    class Solution {
    public:
        
        struct TrieNode{
            
            bool is_end;
            bool starts_with;
            struct TrieNode* children[26];
            
        };
        
        struct TrieNode* createNode(){
            
            struct TrieNode* n = new TrieNode;
            n->is_end = false;
            n->starts_with = false;
            
            for(int i = 0 ; i < 26; i++){
                n->children[i] = NULL;
            }
            
            return n;
            
        }
        
        void insert(TrieNode* root, string s){
            
            int len = s.length();
            
            for(int i = 0; i < len; i++){
                
                if(root->children[s[i] - 'a'] == NULL){
                    root->children[s[i] - 'a'] = createNode();
                    root->children[s[i] - 'a']->starts_with = true;
                }
                
                root = root->children[s[i] - 'a'];
            }
            
            root->is_end = true;
            
        }
        
        
        bool search(TrieNode* root, string s){
            
            int len = s.length();
            
            for(int i = 0 ; i < len; i++){
                
                if(root->children[s[i] - 'a'] == NULL){
                    return false;
                }
                
                root = root->children[s[i] - 'a'];
            }
            
            return root->is_end;
        }
        
        
        bool startsWith(TrieNode* root, string s){
            
            int len = s.length();
            
            for(int i = 0; i < len; i++){
                if(root->children[s[i] - 'a']  == NULL){
                    return false;
                }
                
                root = root->children[s[i] - 'a'];
            }
            
            return root->starts_with;
            
            
        }
    
        void helper(vector<vector<char> >& board, string s, int x, int y, vector<string>& res, bool** track, TrieNode* root){
            
            
            if(x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || track[x][y] == true){
            
            
                return;
            }
            
            s += board[x][y];
            
            
            
            
            if(!startsWith(root,s)){
                return;
            }
            
            if(search(root,s)){
                
                res.push_back(s);
               
            }
            
            
            
            
            
            track[x][y] = true;
            
            helper(board, s,x-1,y,res,track,root);
            helper(board, s,x+1,y,res,track,root);
            helper(board, s,x,y-1,res,track,root);
            helper(board, s,x,y+1,res,track,root);
            
            track[x][y] = false;
            
            
        }
    
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            
            int n = words.size();
            vector<string> res;
            bool** track = new bool*[board.size()];
            
            for(int i = 0 ; i < board.size(); i++){
                
                track[i] = new bool[board[0].size()];
            }
           
            
           for(int i = 0;  i <  board.size(); i++){
               for(int j = 0 ; j < board[0].size(); j++){
                   track[i][j] = false;
               }
           }
            
            
            
            if(n == 0){
                
                return res;
            }
            
            TrieNode* root = createNode();
            for(int i = 0; i < n; i++){
                
                insert(root,words[i]);
                
            }
            
            
           
            
           for (int i = 0; i < board.size(); i++) {
                for (int j = 0; j < board[0].size(); j++) {
                   helper(board,"",i,j,res,track,root);
                }
            }
            
            
            sort(res.begin(),res.end());
            res.erase( unique( res.begin(), res.end() ), res.end() );
            
            return res;
            
            
        }
    };

Log in to reply
 

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