C++ solution using Trie


  • 0
    A
    class Solution {
    private:
        struct TrieNode {
            bool isWord;
            unordered_map<char, TrieNode *> children;
            TrieNode() : isWord(false) {}
        };
        
        void addWord(TrieNode *curr, string &word) {
            for (char c : word) {
                if (!curr->children.count(c))
                    curr->children[c] = new TrieNode();
                curr = curr->children[c];
            }
            curr->isWord = true;
        }
        
        int search(TrieNode *curr, string &s, int i) {
            int j = i - 1;
            while (curr && i < s.length() && curr->children.count(s[i])) {
                curr = curr->children[s[i]];
                if (curr->isWord)
                    j = i;
                ++i;
            }
            return j;
        }
        
    public:
        string addBoldTag(string s, vector<string>& dict) {
            TrieNode *root = new TrieNode();
            for (string &word : dict)
                addWord(root, word);
            
            string ans;
            int i = 0, e = -1;
            while (i < s.length()) {
                int j = search(root, s, i);
                if (j >= i) {
                    if (e == - 1)
                        ans += "<b>";
                    e = max(e, j);
                }
                else {
                    if (e != -1 && i > e) {
                        ans += "</b>";
                        e = -1;
                    }
                }
                ans.push_back(s[i]);
                ++i;
            }
            if (e != -1 && i > e)
                ans += "</b>";
            return ans;
        }
    };
    

Log in to reply
 

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