C++ Trie sol - structured


  • 0
    M

    The class Solution contains a TrieNode* root (the root of a Trie). replace Words calls the following methods in order:

    1. insertAllWords(): insert all root-words into the Trie
    2. splitWords(): split sentence into a vector of words
    3. for each word in the vector, call startsWith(), if return true (found root-word in Trie or simply reach end of word), push to final result
    
    class Solution {
    public:
        Solution():root(new TrieNode()) {}
        
        ~Solution() {delete root;}
        
        string replaceWords(vector<string>& dict, string sentence) {
            insertAllWords(dict); // insert all words into Trie
            vector<string> words = splitWords(sentence, ' '); // split sentence into words
            string result;
            for(const string& word:words) {
                string prefix;
                if(startsWith(word,0,root,prefix)) result+=prefix;
                else result+=word;
                result+=" ";
            }
            if(!result.empty()) result.pop_back(); // pop last redundant empty space
            return result;
        }
    private:
        struct TrieNode {
            TrieNode():child(vector<TrieNode*>(26,NULL)),end(false) {}
            ~TrieNode() {for(auto& node:child) delete node;}
            vector<TrieNode*> child;
            bool end;
        };
        
        TrieNode* root;
        
        void insertAllWords(const vector<string>& dict) {
            for(const auto& word:dict) insertOneWord(word,0,root);
        }
        
        void insertOneWord(const string& word, int i, TrieNode* root) {
            if(!root || i==word.length()) return;
            int k=word[i]-'a';
            if(!root->child[k]) root->child[k]=new TrieNode();
            if(i==word.length()-1) root->child[k]->end=true;
            insertOneWord(word,i+1,root->child[k]);
        }
        
        bool startsWith(const string& word, int i, const TrieNode* root, string& prefix) {
            if(!root || i==word.length()) return false;
            int k=word[i]-'a';
            if(!root->child[k]) return false;
            prefix+=word[i];
            if(root->child[k]->end || i==word.length()-1) return true;
            return startsWith(word,i+1,root->child[k],prefix);
        }
        
        vector<string> splitWords(const string& sentence, char delim) {
            stringstream ss(sentence);
            string tmp;
            vector<string> result;
            while(getline(ss,tmp,delim)) 
                result.push_back(tmp);
            return result;
        }
        
    };
    

Log in to reply
 

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