428. Add Bold Tag in String
You are given a string s and a list of search terms words. Wrap every piece of s that matches at least one term in a pair of bold tags, <b> and </b>.
Matches may overlap each other or sit side by side. Whenever two bolded stretches overlap or touch, they must be covered by one shared pair of tags — the final answer uses as few tag pairs as possible.
Return the annotated string.
Example 1:
Input: s = "helloworld", words = ["llo", "wor"]
Output: "he<b>llowor</b>ld"
Explanation: "llo" bolds indices 2..4 and "wor" bolds indices 5..7. The two stretches touch (4 and 5 are neighbors), so they share one tag pair.
Example 2:
Input: s = "aaabbcc", words = ["aaa", "aab", "bc"]
Output: "<b>aaabbc</b>c"
Explanation: "aaa" covers 0..2, "aab" covers 1..3, and "bc" covers 4..5. Together they bold indices 0..5 as one merged stretch; the final c stays plain.
Constraints:
- 1 ≤ s.length ≤ 1000
- 1 ≤ words.length ≤ 100
- 1 ≤ words[i].length ≤ 50
- s and every words[i] consist of lowercase English letters and digits.
Hints:
Think of every match as an interval [start, start + len). The problem is really: mark all covered positions, then merge touching intervals.
A boolean array bold[i] — "is position i inside some match?" — makes the merging trivial: consecutive true runs become one tag pair.
To find matches faster than checking every word at every position, put the words in a trie and walk it from each starting index, marking the farthest match end you reach.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "helloworld", words = ["llo", "wor"]
Expected output: "he<b>llowor</b>ld"