Bold Words in String - Solution & Explanation

Problem Overview: You receive a list of words and a string s. Any substring of s that matches a word must be wrapped in <b> and </b>. If multiple matches overlap or touch each other, they must be merged into a single bold segment.

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

Scan the string from every index and check whether any word in the dictionary starts at that position. For each index i, iterate through all words and compare characters. When a match is found, mark the corresponding range in a boolean array indicating bold positions. After processing all matches, iterate through the array to build the final string and insert <b> tags around contiguous marked segments.

This approach relies on straightforward array marking and string matching. The downside is repeated comparisons against every word, which becomes slow when the dictionary grows. Still, it clearly demonstrates the mechanics of identifying and merging bold intervals.

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

Build a Trie from all dictionary words. Each node represents a character and marks whether a word ends at that point. While scanning the string s, start a Trie traversal from each index and extend as long as characters match. Every time you hit a terminal node, update the farthest end of a bold segment starting at that index.

This eliminates repeated scanning of all words. Instead, matching follows shared prefixes stored in the Trie, which drastically reduces redundant work. Maintain a boolean array or interval boundary to mark bold positions, then generate the final string by inserting tags when entering or leaving a bold region.

The key insight: overlapping matches are handled naturally by tracking the furthest bold boundary while scanning. Adjacent intervals automatically merge when you convert the boolean marks into the output string.

Recommended for interviews: The Trie approach is typically expected for medium-level string problems involving multiple dictionary matches. The brute force solution proves you understand interval marking and merging, but the Trie version shows stronger knowledge of prefix structures and efficient string matching techniques.