题目描述：

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.

题目大意：

给定一组关键词words和字符串S，将S中所有出现的关键词加粗。需要确保使用的加粗标记最少。

解题思路：

建立辅助数组bold，bold[i]表示S[i]是否需要加粗

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)

 

本文链接：http://bookshadow.com/weblog/2018/01/07/leetcode-bold-words-in-string/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码