We put all the words in our given wordlist into a trie. Then, let's paint any letter in our string that should be bolded. For every starting position `i`

in our string, let's find the longest word that `S[i:]`

starts with, and paint `S[i:i+len(word)]`

.

Afterwards, we have a boolean array where `paint[i] = True`

iff `S[i]`

is bolded. Let's write our letters from left to right. If we are on a bolded letter and there is an unbolded letter to the left (or if we are at the leftmost letter), we should start a `<b>`

tag. Similarly for `</b>`

tags: they start when our bolded letter has an unbolded right neighbor (or we are at the right-most letter.)

```
def addBoldTag(self, S, A):
END = False
_trie = lambda: collections.defaultdict(_trie)
trie = _trie()
for word in A:
cur = trie
for letter in word:
cur = cur[letter]
cur[END] = END
paint = [False] * len(S)
for i in xrange(len(S)):
cur = trie
end = i
for j in xrange(i, len(S)):
if S[j] not in cur: break
cur = cur[S[j]]
if END in cur:
end = j + 1
paint[i:end] = [True] * (end - i)
ans = []
for i, u in enumerate(S):
if paint[i] and (i == 0 or not paint[i-1]):
ans.append('<b>')
ans.append(u)
if paint[i] and (i == len(S) - 1 or not paint[i+1]):
ans.append('</b>')
return "".join(ans)
```

Alternatively, for a simpler but slower idea, we could check if each word starts at each position.

```
def addBoldTag(self, S, A):
paint = [False] * len(S)
for i in xrange(len(S)):
block = S[i:]
for word in A:
if block.startswith(word):
paint[i:i+len(word)] = [True] * len(word)
ans = []
for i, u in enumerate(S):
if paint[i] and (i == 0 or not paint[i-1]):
ans.append('<b>')
ans.append(u)
if paint[i] and (i == len(S) - 1 or not paint[i+1]):
ans.append('</b>')
return "".join(ans)
```