616. Add Bold Tag in String

worst case O(n*sum{dict[i].length}) time
纯暴力
维护一个bold数组标明每个字符是否需要bold
和758. Bold Words in String是同一道题

class Solution {
public:
    string addBoldTag(string s, vector<string>& dict) {
        int n = size(s);
        vector<bool> bold(n);
        for (const auto &w : dict) {
            int p = -1;
            while (true) {
                p = s.find(w, p + 1);
                if (p == -1) break; // npos等于-1
                fill_n(begin(bold) + p, size(w), true);
            }
        }
        string res;
        for (int i = 0; i < n; ++i) {
            if (bold[i] && (i == 0 || !bold[i - 1])) {
                res += "<b>";
            }
            res += s[i];
            if (bold[i] && (i == n - 1 || !bold[i + 1])) {
                res += "</b>";
            }
        }
        return res;
    }
};

class Solution {
public:
    string addBoldTag(string s, vector<string>& dict) {
        int n = s.length();
        vector<bool> bold(n);
        for (const auto &w : dict) {
            int len = w.length(), p = -1;
            while (true) {
                p = s.find(w, p + 1);
                if (p == -1) break;
                for (int i = 0; i < len; ++i) {
                    bold[p + i] = true;
                }
            }
        }
        string res;
        for (int i = 0; i < n;) {
            if (bold[i]) {
                res += "<b>";
                while (i < n && bold[i]) {
                    res += s[i++];
                }
                res += "</b>";
            } else {
                while (i < n && !bold[i]) {
                    res += s[i++];
                }
            }
        }
        return res;
    }
};

trie

class Solution {
public:
    string addBoldTag(string s, vector<string>& dict) {
        root = new TrieNode;
        for (const auto &w : dict) {
            add(w);
        }
        for (int n = s.length(), r = 0; r < n; ++r) {
            add(search(s, r), r);
        }
        string res;
        for (int n = s.length(), i = 0; i < n; ++i) {
            if (!lst.empty()) {
                auto [l, r] = lst.front();
                if (i == l) {
                    res += "<b>";
                }
                if (i == r) {
                    res += s[i];
                    res += "</b>";
                    lst.pop_front();
                    continue;
                }
            }
            res += s[i];
        }
        return res;
    }

    struct TrieNode {
        unordered_map<char, TrieNode *> children;
        bool isEnd = false;
    };

    TrieNode *root = nullptr;

    void add(const string &s) {
        auto p = root;
        for (int n = s.length(), i = n - 1; i >= 0; --i) {
            if (!p->children.count(s[i])) {
                p->children[s[i]] = new TrieNode;
            }
            p = p->children[s[i]];
        }
        p->isEnd = true;
    }

    int search(const string &s, int r) {
        auto p = root;
        int l = r + 1;
        for (int i = r; i >= 0; --i) {
            if (!p->children.count(s[i])) break;
            p = p->children[s[i]];
            if (p->isEnd) {
                l = min(l, i);
            }
        }
        return l;
    }

    void add(int l, int r) {
        if (l > r) return;
        while (!lst.empty() && l <= lst.back().second + 1) {
            l = min(l, lst.back().first);
            lst.pop_back();
        }
        lst.emplace_back(l, r);
    }

    list<pair<int, int>> lst;
};