难度: Medium
Submission
运行时间: 41 ms
内存: 16.1 MB
class Solution:
def boldWords(self, words: List[str], s: 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 相同，用于标记 s 中每个字符是否属于加粗单词。然后遍历单词列表 words，对于每个单词，用 find 方法在 s 中查找该单词出现的位置，并将 mask 数组中对应位置的值设为 True。最后遍历 mask 数组，根据当前字符是否被标记以及前后字符的标记情况，在合适的位置插入 <b> 和 </b> 标签，构造出最终的结果字符串。
时间复杂度: O(mn)
空间复杂度: O(n)
class Solution:
def boldWords(self, words: List[str], s: str) -> str:
n = len(s)
mask = [False] * n # 初始化布尔数组 mask，标记每个字符是否属于加粗单词
for w in words:
idx = 0
while -1 < idx < len(s):
idx = s.find(w, idx) # 在 s 中查找单词 w 出现的位置
if idx != -1:
mask[idx:idx+len(w)] = [True] * len(w) # 将对应位置的 mask 值设为 True
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
Explore
在处理重叠单词时，算法通过将mask数组中对应单词覆盖的每个位置都设为True来实现。因此，如果单词'ab'和'bc'在字符串'sabc'中重叠，首先单词'ab'会使mask数组在位置0和1设为True，然后单词'bc'会使mask数组在位置1和2设为True。结果是，mask数组的前三个位置都标记为True，正确地表示这些位置的字符都应被加粗。这种方法能够自然地处理单词的重叠情况，无需额外逻辑。
如果单词列表中包含重复的单词，当前算法会对每次出现的单词都执行查找和标记操作，这确实是一种冗余操作。更高效的处理方法是先使用集合或其他数据结构去除单词列表中的重复项，然后再进行查找和标记。这样可以减少不必要的查找次数，提高算法的效率。
这种条件判断方式是为了识别加粗区域的开始边界。当mask[i]为True且i为0时，说明字符串的第一个字符需要加粗；若mask[i]为True且mask[i-1]为False时，则表示当前字符是一个新的加粗区域的开始。这种方式能够确保每次进入一个加粗区域时只插入一次<b>标签，并且可以正确处理连续的加粗区域。因此，这个条件判断可以覆盖所有需要加粗的场景，包括连续加粗和非连续加粗的情况。
算法确保了循环不会陷入无限循环。在while循环中，每次找到单词后，idx变量自增1，确保下次find操作从上一次找到的单词的下一个位置开始搜索。如果find方法返回-1，表示字符串中已经没有更多的该单词，此时while循环的条件'-1 < idx < len(s)'不再满足，因此循环会自然终止。这样的逻辑确保了循环的正确性和终止。