NeetCode #831LC-616MediumIntervalsNC Algo100
← Back to All Problems#831 · #616 · Add Bold Tag in String(给字符串添加加粗标签)
📌 Problem Statement & Constraints
You are given a string
s and a list of words. Wrap in <b> and </b> every substring of s that matches any word, merging overlapping or adjacent matches into a single bold region. Return the resulting string. Constraints: 1 <= s.length <= 1000, 0 <= words.length <= 100, 1 <= words[i].length <= s.length, s and words[i] consist of lowercase English letters.💡 Core Algorithmic Approaches
- Every occurrence of every word defines an interval
[start, start + len - 1]over the indices ofs. - Mark a boolean array over the string for every covered index; overlapping and adjacent matches then merge automatically into maximal runs of marked positions.
- Scan the string and wrap each maximal run of marked indices with the bold tags.
- Merging the intervals before emitting is what prevents nested or duplicated tags.
💻 Benchmark Python3 Implementation
class Solution:
def addBoldTag(self, s: str, words: List[str]) -> str:
n = len(s)
bold = [False] * n
for w in words:
start = s.find(w)
while start != -1:
for i in range(start, start + len(w)):
bold[i] = True # mark this occurrence
start = s.find(w, start + 1) # allow overlapping occurrences
res = []
i = 0
while i < n:
if bold[i]:
res.append("<b>")
while i < n and bold[i]: # maximal run of marked indices
res.append(s[i])
i += 1
res.append("</b>")
else:
res.append(s[i])
i += 1
return "".join(res)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(W * n) in the worst case, where W is the number of words: each find scan plus marking.
💾 Space Complexity
O(n) for the mark array and the output.
⚠️ Interview Pitfalls & Follow-ups
- Advancing the search by
len(w): overlapping occurrences (likeaainaaa) require advancing by one, so the nextfindstarts atstart + 1. - Emitting a tag per occurrence: overlapping matches must merge into one region, which the mark array guarantees.
- Using
str.replace: a naive replace cannot merge overlaps or adjacent matches and would nest tags incorrectly. - Forgetting that adjacent matches merge:
abandbcinabccover every index, so a single bold region is correct.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.