```
class Solution(object):
def addBoldTag(self, s, dict):
"""
:type s: str
:type dict: List[str]
:rtype: str
"""
#find all overlapping matches
matches = []
for word in dict:
start = 0
while True:
start = s.find(word, start)
if start == -1:
break
else:
matches.append([start, start + len(word)])
start += 1
#merge all matches like intervals
matches = sorted(matches)
self.mergeInterval(matches)
#concatenate string
ret = ""
pos = 0
for start, end in matches:
ret += s[pos:start] + '<b>' + s[start:end] + '</b>'
pos = end
ret += s[pos:]
return ret
def mergeInterval(self, intervals):
start, end = 0, 0
n = len(intervals)
while end < n:
intervals[start] = intervals[end]
while end < n and intervals[end][0] <= intervals[start][1]:
intervals[start][1] = max(intervals[start][1], intervals[end][1])
end += 1
start += 1
del intervals[start:]
```