c++ Trie solution


  • 0
    J
    class Solution {
        typedef struct TrieNode
        {
            bool isWord;
            unordered_map<char, TrieNode*> children;
            TrieNode():isWord(false){};
        }TrieNode;
        
        void AddWord(TrieNode* root, string word)
        {
            TrieNode* cur=root;
            for(auto c:word)
            {
                if(cur && !cur->children.count(c))
                {
                    cur->children[c]=new TrieNode;
                }
                cur=cur->children[c];
            }
            cur->isWord=true;
        }
        
        bool SearchWord(TrieNode* root, string word, string& rootpart)
        {
            TrieNode* cur=root;
            for(auto c:word)
            {
                if(cur && cur->isWord)
                {
                    return true;
                }
                
                if(cur && !cur->children.count(c))
                    return false;
                rootpart.push_back(c);
                cur=cur->children[c];
            }
            return false;
        }
    public:
        string replaceWords(vector<string>& dict, string sentence) {
            int len=dict.size();
            if(len==0)
                return sentence;
            TrieNode* root=new TrieNode;
            string ans;
            for(auto word:dict)
            {
                AddWord(root, word);
            }
            int l=sentence.length();
            for(int start=0, end=0; end<=l; )
            {
                if(end < l && isChar(sentence[end]))
                {
                    end++;
                }
                else
                {
                    string sub=sentence.substr(start, end-start);
                    string rootpart;
                    if(SearchWord(root, sub, rootpart))
                    {
                        ans+=rootpart+" ";
                    }
                    else
                    {
                        ans+=sub+" ";
                    }
                    start=end+1;
                    end++;
                }
            }
            ans.pop_back();
            return ans;
        }
        
        bool isChar(char c)
        {
            if(c>='a' && c<='z')
                return true;
            if(c>='A' && c<='Z')
                return true;
            return false;
        }
    };
    

Log in to reply
 

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