数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在C++中添加粗体标签到字符串
假设我们有一个字符串s和一个字符串列表dict，我们需要添加一对闭合的粗体标签<b>和</b>来包裹s中存在于dict中的子字符串。当两个这样的子字符串重叠时，我们只需要用一对闭合的粗体标签将它们一起包裹。此外，如果两个用粗体标签包裹的子字符串是连续的，我们需要将它们合并。
因此，如果输入类似于s = "abcxyz123"，dict是["abc","123"]，则输出将是"<b>abc</b>xyz<b>123</b>"
为了解决这个问题，我们将遵循以下步骤：
n := s的长度
定义一个大小为n的数组bold
ret := 空字符串
for i := 0, end := 0, i < s的长度, i := i + 1, do −
for j := 0, j < dict的长度, j := j + 1, do −
如果s从索引(i到dict[j]的长度-1)的子字符串与dict[j]相同，则：
end := end和i + dict[j]的长度的最大值
bold[i] := end > i
for i := 0, i < s的长度, i := j, do −
如果bold[i]为零，则：
ret := ret + s[i]
j := i + 1
忽略以下部分，跳到下一个迭代
j := i
while (j < s的长度 and bold[j]不为零), do −
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>
更新于: 2020年11月16日
2K+浏览量
广告