DSA problem
Add Bold Tag in String
You are given a string s and an array of strings words.
You should add a closed pair of bold tag <b> and </b> to wrap the substrings in s that exist in words.
- If two such substrings overlap, you should wrap them together with only one pair of closed bold tag.
- If two substrings wrapped by bold tags are consecutive, you should combine them.
Return s after adding the bold tags.
Examples
Example 1
Input:
s = "abcxyz123", words = ["abc","123"]Output:
"<b>abc</b>xyz<b>123</b>"Explanation: The two strings of words are substrings of s as following: "abcxyz123". We add <b> before each substring and </b> after each substring.
Example 2
Input:
s = "aaabbb", words = ["aa","b"]Output:
"<b>aaabbb</b>"Explanation: "aa" appears as a substring two times: "aaabbb" and "aaabbb". "b" appears as a substring three times: "aaabbb", "aaabbb", and "aaabbb". We add <b> before each substring and </b> after each substring: "<b>a<b>a</b>a</b><b>b</b><b>b</b><b>b</b>". Since the first two tags overlap, and the same for the last three, we merge them: "<b>aaa</b><b>bbb</b>". Since now the two substrings are consecutive, we merge them: "<b>aaabbb</b>".
Example 3
Input:
s = "leetcode", words = ["code","leet"]Output:
"<b>leetcode</b>"Explanation: Both "leet" and "code" are substrings; their ranges [0,3] and [4,7] are consecutive, so they are combined into one bold region.
Constraints
- 1 <= s.length <= 1000
- 0 <= words.length <= 100
- 1 <= words[i].length <= 1000
- s and words[i] consist of English letters and digits.
- All the values of words are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.