LeetCode 616 Add Bold Tag in String (Python)

Posted by 小明MaxMing on November 3, 2024

题目

You are given a string s and an array of strings words.

You should add a closed pair of bold tag and to wrap the substrings in s that exist in words.

  • If two such substrings overlap, you should wrap them together with only one pair of closed bold-tag.
  • If two substrings wrapped by bold tags are consecutive, you should combine them. Return s after adding the bold tags.

解题思路

用一个数组维护所有需要加粗的字母位置,遍历每个单词,用find找到单词match开始的位置i,后面单词长度的位置,都标为true,再从i+1位置继续寻找。最后遍历这个数组,把连续标为True的位置前后加上tag

代码

class Solution:
    def addBoldTag(self, s: str, words: List[str]) -> str:
        n = len(s)
        bold = [False] * (n + 1)
        for word in words:
            i = s.find(word)
            while i != -1:
                for j in range(i, i + len(word)):
                    bold[j] = True
                i = s.find(word, i + 1)
        open, close, res = "<b>", "</b>", []
        for i in range(n):
            if bold[i] and not bold[i - 1]:
                res.append(open)
            res.append(s[i])
            if bold[i] and not bold[i + 1]:
                res.append(close)
        return "".join(res)

视频讲解 YouTube<--欢迎点击订阅

视频讲解 bilibili<--欢迎点击订阅