给定一个关键词集合 words 和一个字符串S，将所有S中出现的关键词加粗。
所有在标签 <b> 和</b>中的字母都会加粗。
返回的字符串需要使用尽可能少的标签，当然标签应形成有效的组合。
例如，给定words = ["ab", "bc"] 和 S = "aabcd"，需要返回"a<b>abc</b>d"。
注意返回"a<b>a<b>b</b>c</b>d"会使用更多的标签，因此是错误的。
注：
words 长度的范围为[0, 50]。
words[i] 长度的范围为[1, 10]。
S 长度的范围为[0, 500]。
所有words[i]和S中的字符都为小写字母。
自我解答
建立 bold_index = [0] * length
使用朴素匹配，如果匹配到的坐标区间，把 bold_index 中对应的都设置为 1
class Solution:
def boldWords(self, words: List[str], S: str) -> str:
self.length = len(S)
self.bold_index = [0 for x in range(self.length)]
self.S = S
for word in words:
self.find_match(word)
in_bold = False
bolded = []
for i in range(0, self.length):
if self.bold_index[i]:
if not in_bold:
bolded.append("<b>")
in_bold = True
bolded.append(self.S[i])
else:
if in_bold:
in_bold = False
bolded.append("</b>")
bolded.append(self.S[i])
if in_bold:
bolded.append("</b>")
return "".join(bolded)
def find_match(self, word):
word_len = len(word)
j = 0
while self.length - j >= word_len:
if self.S[j] == word[0] and self.S[j:j + word_len] == word:
for i in range(j, j + word_len):
self.bold_index[i] = 1
j += 1
力扣提交显示击败 15%，我想是字符串匹配太慢了，于是换成了 kmp，一提交更慢了
题解
改用内置函数 find, 呵呵，击败 98%
class Solution5:
def boldWords(self, words: List[str], S: str) -> str:
length = len(S)
bold_indexs = [0] * length
for word in words:
i, wlen = 0, len(word)
while i < length:
i = S.find(word, i)
if i == -1:
break
bold_indexs[i:i + wlen] = [1] * wlen
i += 1
res, bon = [], False
for i in range(0, length):
if bold_indexs[i] and not bon:
res.append("<b>")
bon = True
elif not bold_indexs[i] and bon:
res.append("<b/>")
bon = False
res.append(S[i])
if bon:
res.append("<b/>")
return "".join(res)