C++ easy understand solution


  • 0
    L

    ...

    class TrieNode{
    public:
    bool isWord;
    TrieNode* children[26];
    TrieNode(){
    isWord=false;
    for(int i=0;i<26;i++){
    children[i]=NULL;
    }
    }
    };

    class Trie{
    public:
    TrieNode* root;
    Trie(){
    root=new TrieNode();
    }

    void insert(string word){
        TrieNode* curr=root;
        for(int i=0;i<word.size();i++){
            int index=word[i]-'a';
            if(curr->children[index]==NULL){
                curr->children[index]=new TrieNode();
            }
            curr=curr->children[index];
        }
        curr->isWord=true;
    }
    
    bool search(string word){
         TrieNode* curr=root;
         for(int i=0;i<word.size();i++){
             int index=word[i]-'a';
             if(curr->children[index]==NULL){
                 return false;
             }
             curr=curr->children[index];
         }
         return curr->isWord;
    }
    bool startWith(string prefix){
        TrieNode* curr=root;
        for(int i=0;i<prefix.size();i++){
            int index=prefix[i]-'a';
            if(curr->children[index]==NULL){
                return false;
            }
            curr=curr->children[index];
        }
        return false; 
    }
    

    };

    class Solution {

    public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    vector<string> result;
    if(words.size()==0){
    return result;
    }
    //creating trie buffer
    Trie buffer;
    for(int i=0;i<words.size();i++){
    buffer.insert(words[i]);
    }

        //searching 
        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
        string temp;
        
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                //dfs search
                dfs(i, j,board,buffer, visited, temp, result);
            }
        }
        
        return result;
    }
    
    void dfs(int i, int j, vector<vector<char>>& board, Trie& buffer, vector<vector<bool>>& visited, string& temp, vector<string>& result){
        //bound
        if(i<0||i>=board.size()||j<0||j>board[0].size()||visited[i][j]){
            return;
        }
        
        temp.push_back(board[i][j]);
        visited[i][j]=true;
        
        if(buffer.startWith(temp)){
            if(buffer.search(temp)){
                result.push_back(temp);
                
                dfs(i-1,j,board,buffer,visited,temp,result);
                dfs(i+1,j,board,buffer,visited,temp,result);
                dfs(i,j-1,board,buffer,visited,temp,result);
                dfs(i,j+1,board,buffer,visited,temp,result);
            }
        }
        
        temp.pop_back();
        visited[i][j]=false;
    }
    

    };

    ...


Log in to reply
 

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