# 758. Bold Words in String 字符串中的加粗单词

@TOC

## # 题目描述

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.

## # 解题方法

### # 遍历

C++代码如下：

``````class Solution {
public:
string boldWords(vector<string>& words, string S) {
const int N = S.size();
vector<bool> isBold(N, false);
for (string& word : words) {
for (int i = 0; i < N; ++i) {
string sub = S.substr(i, word.size());
if (sub == word) {
for (int k = i; k < i + word.size(); ++k) {
isBold[k] = true;
}
}
}
}
string res;
for (int i = 0; i < N; ++i) {
if (isBold[i] && (i == 0 || !isBold[i - 1])) {
res += "<b>";
}
res += S[i];
if (isBold[i] && (i == N - 1 || !isBold[i + 1])) {
res += "</b>";
}
}
return res;
}
};
``````

## # 日期

2019 年 9 月 18 日 —— 今日又是九一八