문자열 s와 dict라는 문자열 목록이 있다고 가정하고 해당 dict에 있는 s의 하위 문자열을 래핑하기 위해 굵은 굵은 태그 및 의 닫힌 쌍을 추가해야 합니다. 두 개의 하위 문자열이 겹칠 때 닫힌 볼드 태그 한 쌍으로만 함께 포장해야 합니다. 또한 굵은 태그로 묶인 두 개의 하위 문자열이 연속적이면 결합해야 합니다.
따라서 입력이 s ="abcxyz123" dict is ["abc","123"]인 경우 출력은 "abcxyz123"
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=s
의 크기 -
n 크기의 굵게 배열 정의
-
ret :=빈 문자열
-
for initialize i :=0, end :=0, i
-
j 초기화의 경우:=0, j
-
인덱스(i에서 dict[j]의 크기 - 1까지)의 s 부분 문자열이 dict[j]와 같으면 -
-
end :=end의 최대값과 i + dict[j]의 크기
-
-
-
굵게[i] :=끝> i
-
-
for initialize i :=0, i
-
굵게[i]가 0이면 -
-
렛 :=렛 + s[i]
-
j :=i + 1
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
j :=나는
-
동안 (j
-
(j를 1씩 증가)
-
-
ret :=인덱스 i에서 j까지 ret의 부분 문자열 - i - 1 연결 "" 연결 s
-
-
리턴 렛
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#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>