資料結構
網路
關係資料庫管理系統(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+瀏覽量
廣告