# Short C++ solutions, Counting pair and counting bold

• counting pair

``````class Solution {
public:
string addBoldTag(string s, vector<string>& dict) {
int n = s.size();
vector<int> open(n + 1), closed(n + 1);
for ( string & w : dict ) {
int i = -1;
while ( (i = s.find(w, i + 1)) != string::npos ) {
++open[i];
++closed[i + w.size()];
}
}
string tagged;
int pre = 0;
for ( int i = 0, t = 0; i <= n; ++i ) {
if ( open[i] && 0 == t && ! closed[i] ) {
tagged += s.substr(pre, i - pre) + "<b>";
pre = i;
}
t += open[i];
t -= closed[i];
if ( closed[i] && 0 == t && ! open[i] ) {
tagged += s.substr(pre, i - pre) + "</b>";
pre = i;
}
}
return tagged + s.substr(pre);
}
};

// 70 / 70 test cases passed.
// Status: Accepted
// Runtime: 23 ms
``````

counting bold

``````class Solution {
public:
string addBoldTag(string s, vector<string>& dict) {
vector<bool> bold(s.size() + 2);
vector<string> sdict(dict);
auto cmp = [] (string & a, string & b) { return a.size() > b.size(); };
sort(sdict.begin(), sdict.end(), cmp);
for ( int i = 0, j; i < s.size(); ++i ) {
for ( j = 0; j < sdict.size(); ++j )
if ( s.find(sdict[j], i) == i )
break;
if ( j < sdict.size() )
fill(bold.begin() + i + 1, bold.begin() + i + 1 + sdict[j].size(), true);
}
string t;
for ( int i = 1; i <= s.size(); ++i ) {
if ( ! bold[i-1] && bold[i] ) t += "<b>";
t += s[i-1];
if ( bold[i] && ! bold[i+1] ) t += "</b>";
}
return t;
}
};

// 70 / 70 test cases passed.
// Status: Accepted
// Runtime: 292 ms
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.