C++ Trie solution, 142ms, short and clean


  • 0
    H
    class trie{
    public:
        bool isWord;
        unordered_map<char, trie*> next;
        trie(){
            isWord=false;
        }
    };
    
    class Solution {
    public:
        string addBoldTag(string s, vector<string>& dict) {
            
            // Create trie
            trie* root = new trie();
            for(auto& word : dict){
                trie* node = root;
                for(char& c : word){
                    if(node->next.find(c)==node->next.end()){
                        node->next[c]=new trie();
                    }
                    node = node->next[c];
                }
                node->isWord=true;
            }
            
            // "last" is the index of last character that currently belong to word
            string res="";
            int last = -1;
            for(int i=0; i<s.size(); i++){
                trie* node = root;
                for(int j=i; j<s.size(); j++){
                    if(node->next.find(s[j])==node->next.end())
                        break;
                    node=node->next[s[j]];
                    if(node->isWord){
                        if(i>last)
                            res+="<b>";
                        last=max(last,j);
                    }
                }
                res+=s[i];
                if(i==last)
                    res+="</b>";
            }
            
            //Delete adjacent </b> and <b>
            for(int i =0; i<res.size()-6; i++){
                if(res.substr(i,7)=="</b><b>")
                    res=res.substr(0,i)+res.substr(i+7);
            }
            return res;
        }
    };
    

Log in to reply
 

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