给字符串添加加粗标签

难度: Medium

Submission

运行时间: 41 ms

内存: 16.3 MB

class Solution:
    def addBoldTag(self, s: str, words: List[str]) -> str:
        n = len(s)
        mask = [False] * n  
        for w in words:
            idx = 0
            while -1 < idx < len(s):
                idx = s.find(w, idx)
                if idx != -1:
                    mask[idx:idx+len(w)] = [True] * len(w)
                    idx += 1   
        
        res = ''
        for i in range(n):
            if mask[i] and (i == 0 or not mask[i - 1]):
                res += '<b>'
            res += s[i]
            if mask[i] and (i == n - 1 or not mask[i + 1]):
                res += '</b>'
        return res

Explain

该题解采用了标记数组的方法来确定字符串中哪些字符需要被加粗。首先，创建一个布尔型数组mask，其长度与输入字符串s相同，用于标记每个位置是否需要加粗。遍历所有的关键词words，并在字符串s中查找每个单词的出现位置。每当找到单词出现的位置时，就将mask数组对应位置标记为True，表示这部分字符需要加粗。在标记完成后，根据mask数组的情况，遍历字符串s构造最终的结果字符串。如果当前字符需要加粗，并且是第一个字符或者前一个字符不需要加粗，就在结果字符串中加入''标签。接着添加当前字符，如果当前字符是需要加粗的，并且是最后一个字符或者后一个字符不需要加粗，就在结果字符串中加入''标签。

时间复杂度: O(m * n * k)

空间复杂度: O(n)

class Solution:
    def addBoldTag(self, s: str, words: List[str]) -> str:
        n = len(s)  # 获取字符串长度
        mask = [False] * n  # 初始化mask数组，长度等于s，用于标记需要加粗的字符
        for w in words:  # 遍历所有关键词
            idx = 0
            while -1 < idx < len(s):  # 在字符串s中查找关键词w
                idx = s.find(w, idx)  # 从当前索引开始查找关键词
                if idx != -1:  # 如果找到了关键词
                    mask[idx:idx+len(w)] = [True] * len(w)  # 标记关键词覆盖的字符
                    idx += 1   # 更新索引，继续查找下一个可能的起始位置
        
        res = ''  # 初始化结果字符串
        for i in range(n):  # 遍历字符串s
            if mask[i] and (i == 0 or not mask[i - 1]):  # 如果当前字符需要加粗，并且是加粗段的开始
                res += '<b>'  # 添加开启加粗的标签
            res += s[i]  # 添加当前字符
            if mask[i] and (i == n - 1 or not mask[i + 1]):  # 如果当前字符需要加粗，并且是加粗段的结束
                res += '</b>'  # 添加关闭加粗的标签
        return res  # 返回结果字符串

Explore

是的，这种方法可以有效处理包含重叠单词的情况。当检测到关键词在字符串中的任何位置时，算法会将该关键词覆盖的所有字符在mask数组中对应位置标记为True。例如，在处理字符串's = "abc"'且关键词列表为['ab', 'bc']时，首先找到'ab'并将位置0和1标记为True，接着找到'bc'并将位置1和2标记为True。因此，整个字符串位置0、1、2都会被标记为True，确保整个字符串被加粗。

选择在匹配后只将索引向前移动一位而不是跳过整个单词的原因是为了处理关键词可能的重叠情况。例如，若关键词为'aba'，在字符串's = "ababa"'中，第一个'aba'从索引0开始，如果跳过整个单词长度，将错过从索引1开始的第二个'aba'。虽然这样做会导致某些字符被重复检查，但这是必要的，以确保不遗漏任何可能的关键词重叠。

如果字符串s中不存在任何一个关键词，那么mask数组将保持全部为False。在构建最终结果字符串的过程中，由于mask数组的值都为False，不会触发添加任何加粗标签(''或'')的条件。因此，结果字符串将仅包括原始字符串s的字符，没有任何加粗标签，这正是预期的行为，因此代码可以正确地处理这种情况。

在这种方法中，不会出现嵌套的加粗标签。算法设计中已确保在加入开启标签''之前检查当前字符是否为加粗段的开始（即当前字符需要加粗且前一个字符不需要加粗），并在加入结束标签''后检查当前字符是否为加粗段的结束（即当前字符需要加粗且后一个字符不需要加粗）。这种检查方式确保了加粗标签的正确开启和关闭，避免了嵌套标签的生成。