在 C++ 中为字符串添加粗体标记
c++server side programmingprogramming
假设我们有一个字符串 s 和一个名为 dict 的字符串列表，我们必须添加一对闭合的粗体标记 <b> 和 </b> 来包装 s 中存在于该 dict 中的子字符串。当两个这样的子字符串重叠时，我们只需用一对闭合的粗体标记将它们包装在一起。此外，如果两个用粗体标记包裹的子字符串是连续的，我们需要将它们组合起来。
因此，如果输入类似 s = "abcxyz123" dict 为 ["abc","123"]，则输出将为 "<b>abc</b>xyz<b>123</b>"
为了解决这个问题，我们将遵循以下步骤 −
n := size of s
定义一个大小为 n 的数组 bold
ret := 空字符串
初始化 i := 0，end := 0，当 i < size of s，更新(将 i 增加 1)，执行 −
初始化 j := 0，当 j <字典的大小，更新(将 j 增加 1)，执行 −
如果 s 的子字符串从索引(i 到 dict[j] 的大小 - 1)与 dict[j] 相同，则 −
end := end 和 i 的最大值 + dict[j] 的大小
bold[i] := end > i
初始化 i := 0，当 i < s 的大小，更新 i = j，执行 −
如果 bold[i] 为零，则 −
ret := ret + s[i]
j := i + 1
忽略以下部分，跳至下一次迭代
j := i
当 (j < s 的大小且 bold[j] 非零) 时，执行 −
(将 j 增加 1)
ret := ret 的子字符串从索引 i 到 j - 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>
