## 题目描述：

LeetCode 758. Bold Words in String

Given a set of keywords `words` and a string `S`, make all appearances of all keywords in `S` bold. Any letters between `<b>` and `</b>` tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given that `words = ["ab", "bc"]` and `S = "aabcd"`, we should return `"a<b>abc</b>d"`. Note that returning `"a<b>a<b>b</b>c</b>d"` would use more tags, so it is incorrect.

Note:

1. `words` has length in range `[0, 50]`.
2. `words[i]` has length in range `[1, 10]`.
3. `S` has length in range `[0, 500]`.
4. All characters in `words[i]` and `S` are lowercase letters.

## Python代码：

``````class Solution(object):
def boldWords(self, words, S):
"""
:type words: List[str]
:type S: str
:rtype: str
"""
N = len(S)
bold = [0] * (N + 2)
for word in words:
start = 0
while True:
idx = S[start:].find(word)
if idx < 0: break
for x in range(start + idx, start + idx + len(word)):
bold[x + 1] = 1
start += idx + 1
S = list(S) + ['']
ans = []
for x in range(1, N + 1):
if bold[x] == 1 and bold[x - 1] == 0:
ans.append('<b>')
ans.append(S[x - 1])
if bold[x] == 1 and bold[x + 1] == 0:
ans.append('</b>')
return ''.join(ans)
``````

Pingbacks已关闭。