# Share My 23ms Solution based on Merge Intervals

• This solution based on the problem: 56. Merge Intervals.

1. Find all the substring of `s` that is in dict, and represents it as an interval `[a, b]`, where `a` is the beginning index of the substring and `b` is the next of the end of substring. For example, `s = "abcxyz123"`, `"abc"` is represented as `[0, 3]`.

2. Merge the above intervals. For example `s = "abcxyz123"` and `dict = ["abc","123"]`, the merged intervals is [[0, 3], [6, 9]]

3. Insert "<b>" and "<\b>" at the begin and end of each interval.

``````class Solution {
public:
string addBoldTag(string s, vector<string>& dict) {
vector<pair<int, int>> intervals;
vector<pair<int, int>> res;

// Find intervals
for (string w : dict) {
size_t pos = 0, next = 0;
while ((pos = s.find(w, next)) != string::npos) {
intervals.push_back(make_pair((int)pos, (int)pos + w.size()));
next = pos + 1;
}
}

// Merge intervals
sort(intervals.begin(), intervals.end());
for (int i = 0; i < intervals.size(); i++) {
if (!res.empty() && intervals[i].first <= res.back().second) {
res.back().second = max(intervals[i].second, res.back().second);
} else {
res.push_back(intervals[i]);
}
}

// Insert tags
int offset = 0;
for (auto p : res) {
s.insert(p.first + offset, "<b>");
offset += 3;
s.insert(p.second + offset, "</b>");
offset += 4;
}
return s;
}
};
``````

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