假设我们有一个字符串s和一个称为dict的字符串列表，我们必须添加一对封闭的粗体标签<b>和</ b>，将子字符串包装在该dict中存在的s中。当两个这样的子字符串重叠时，我们只需要用一对封闭的加粗标签将它们包装在一起。另外，如果两个由粗体标签包裹的子字符串是连续的，我们需要将它们组合在一起。
因此，如果输入像s =“ abcxyz123” dict是[“ abc”，“ 123”]，则输出将是“ <b> abc </ b> xyz <b> 123 </ b>”
为了解决这个问题，我们将遵循以下步骤-
n：= s的大小
定义大小为n的数组粗体
ret：=空字符串
对于初始化i：= 0，结束：= 0，当i <s的大小时，更新（将i增加1），执行-
如果从索引（i到dict [j]-1的大小）的s子字符串与dict [j]相同，则-
end：= end的最大值和i + dict [j]的大小
对于初始化j：= 0，当j <字典大小时，更新（将j增加1），-
粗体[i]：=结束>我
对于初始化i：= 0，当i <s的大小时，更新i = j，执行-
（将j增加1）
ret：= ret + s [i]
j：= i + 1
忽略以下部分，跳至下一个迭代
如果bold [i]为零，则-
j：=我
而（j <s的大小和粗体[j]为非零），则执行-
ret：=从索引i到j的ret的子字符串-i-1连接“ <b>”连接s
返回ret
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string addBoldTag(string s, vector<string>& dict) {
int n = s.size();
vector<int> bold(n);
string ret = "";
for (int i = 0, end = 0; i < s.size(); i++) {
for (int j = 0; j < dict.size(); j++) {
if (s.substr(i, dict[j].size()) == dict[j]) {
end = max(end, i + (int)dict[j].size());
}
}
bold[i] = end > i;
}
int j;
for (int i = 0; i < s.size(); i = j) {
if (!bold[i]) {
ret += s[i];
j = i + 1;
continue;
}
j = i;
while (j < s.size() && bold[j])
j++;
ret += "<b>" + s.substr(i, j - i) + "</b>";
}
return ret;
}
};
main(){
Solution ob;
vector<string> v = {"abc","123"};
cout << (ob.addBoldTag("abcxyz123", v));
}"abcxyz123", ["abc","123"]
输出结果
<b>abc</b>xyz<b>123</b>