758. Bold Words in String

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

class Solution {
public:
    string boldWords(vector<string>& words, string S) {
        int n = size(S);
        vector<bool> bold(n);
        for (const auto &w : words) {
            int p = -1;
            while (true) {
                p = S.find(w, p + 1);
                if (p == -1) break;
                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;
    }
};