Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between <b> and </b> tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given that words = ["ab", "bc"] and S = "aabcd", we should return "a<b>abc</b>d". Note that returning "a<b>a<b>b</b>c</b>d" would use more tags, so it is incorrect.

Note:

  1. words has length in range [0, 50].
  2. words[i] has length in range [1, 10].
  3. S has length in range [0, 500].
  4. All characters in words[i] and S are lowercase letters.

先用双重循环找到有所得子串，对于每一个子串，判断是否要加粗，如果是，那么就把这个子串的所有位置设置为1（要加粗）。最后再把所有标记为要加粗的字符两边加上<b></b>。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    string boldWords(vector<string>& _words, string S) {
        if (S.empty())
            return "";
        unordered_set<string> words(_words.begin(), _words.end());
        vector<int> flag(S.length(), 0);
        for (int i = 0; i < S.length(); i++) {
            for (int j = 0; j <= i; j++) {
                string tmp = S.substr(j, i - j + 1);
                if (words.count(tmp)) {
                    for (int k = j; k <= i; k++) {
                        flag[k] = 1;
                    }
                    break;
                }
            }
        }

        string ans;
        if (flag.front()) {
            ans += "<b>";
        }
        for (int i = 0; i < S.length() - 1; i++) {
            ans.push_back(S[i]);
            if (flag[i] == 0 && flag[i + 1] == 1) {
                ans += "<b>";
            }
            else if (flag[i] == 1 && flag[i + 1] == 0) {
                ans += "</b>";
            }
        }
        ans.push_back(S.back());
        if (flag.back()) {
            ans += "</b>";
        }
        return ans;
    }
};