Skip to main content
Talentd

Bold Words in String - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableStringTrie5 min readAsked at: Google
Practice this problem

Problem Statement

Given an array of keywords words and a string s, make all appearances of all keywords words[i] in s bold. Any letters between <b> and </b> tags become bold.

Return s after adding the bold tags. The returned string should use the least number of tags possible, and the tags should form a valid combination.

 

Example 1:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"
Explanation: Note that returning "a<b>a<b>b</b>c</b>d" would use more tags, so it is incorrect.

Example 2:

Input: words = ["ab","cb"], s = "aabcd"
Output: "a<b>ab</b>cd"

 

Constraints:

  • 1 <= s.length <= 500
  • 0 <= words.length <= 50
  • 1 <= words[i].length <= 10
  • s and words[i] consist of lowercase English letters.

 

Note: This question is the same as 616. Add Bold Tag in String.

Approach Overview

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.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Word MatchingO(n * k * L)O(n)Small dictionary or quick prototype where implementation simplicity matters
Trie-Based Prefix MatchingO(n * L)O(W + n)General case with many words or shared prefixes; typical optimal interview solution

Video Solution

花花酱 LeetCode 758. Bold Words in String - 刷题找工作 EP155 • Hua Hua • 4,164 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Bold Words in String easy or hard?
Bold Words in String is generally rated Medium. The challenge comes from combining efficient substring matching with correct interval merging. Once the matching ranges are marked correctly, generating the final tagged string becomes straightforward.
Bold Words in String Python/Java solution
Implementations typically build a Trie from the word list, scan the string to mark bold intervals, then construct the output with <b> and </b> tags. The same logic works in Python, Java, C++, and Go because it relies on basic Trie traversal and array marking.
How to solve Bold Words in String in O(n)?
Near-linear performance is achieved by building a Trie of all words and scanning the string once. At each position, traverse the Trie to find the longest matching prefix and update the farthest bold boundary. A boolean array or interval range records bold characters, and the final pass inserts <b> tags around contiguous segments.
What is the best approach for Bold Words in String?
The most efficient approach builds a Trie from all dictionary words and scans the string from each index. Trie traversal finds all prefixes starting at that index without repeatedly comparing every word. This reduces redundant checks and runs in roughly O(n * L) time where n is the string length and L is the maximum word length.
Is Bold Words in String asked at Google/Amazon/Meta?
This style of problem appears in interviews that test string processing and dictionary matching. Variants involving substring highlighting, interval merging, or Trie-based matching have been reported in interviews at companies like Google, Amazon, and Meta.
What data structure is used in Bold Words in String?
Common solutions use a Trie for efficient prefix lookup along with an array or boolean marker to track bold ranges. The Trie stores dictionary words with shared prefixes, while the array helps merge overlapping or adjacent matches when constructing the final string.
What is the time complexity of Bold Words in String?
The optimal Trie-based solution runs in O(n * L) time, where n is the length of the string and L is the maximum length of any word in the dictionary. Building the Trie takes O(W) where W is the total number of characters across all words. Space complexity is O(W + n) for the Trie and the bold marker array.

Ready to solve this problem?

Practice Bold Words in String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays