Add Bold Tag in String - Video Solutions

Problem Overview: Given a string s and a list of dictionary words, wrap every substring in s that appears in the dictionary with <b> and </b>. Overlapping or adjacent matches must be merged into a single bold region.

Approach 1: Brute Force Matching + Interval Merge (O(n * k * L) time, O(n) space)

Scan the string from every index and check whether any dictionary word matches starting at that position using substring comparison. For each match, mark the covered indices in a boolean array or store intervals like [start, end]. After processing all matches, merge overlapping or adjacent intervals and construct the final string by inserting <b> and </b> around bold segments. This approach is straightforward and easy to implement, but repeated substring comparisons make it slower when the dictionary is large.

Approach 2: Boolean Marking with Longest Match Tracking (O(n * k * L) time, O(n) space)

Instead of storing intervals, maintain a boolean array bold[i] indicating whether character i should be bold. While iterating through s, check every dictionary word with a prefix comparison like s.startswith(word, i). Track the farthest index that should remain bold and mark characters up to that boundary. Finally, build the output string while opening a <b> tag when entering a bold region and closing it when leaving one. This method avoids explicit interval merging and is often the cleanest implementation.

Approach 3: Trie-Based String Matching (O(n * L) time, O(W * L) space)

Build a Trie from the dictionary words. Starting at each index in s, traverse the Trie while characters continue to match. Whenever a word end is reached, update the farthest bold boundary. This reduces redundant comparisons because common prefixes are shared in the Trie. The technique is common in string matching problems and works well when the dictionary contains many overlapping prefixes. Use an array or interval list to mark bold positions and generate the final string.

Recommended for interviews: The boolean marking approach is usually expected. It demonstrates clear reasoning about substring matching and interval merging while keeping the implementation simple. Mentioning a Trie optimization shows deeper understanding of scalable string matching techniques.