Add Bold Tag in String

Problem Statement

Given a string s and a list of substrings named words, the task is to wrap certain substrings of s that appear in words with HTML bold tags (<b> and </b>). This wrapping must respect a few conditions: if two substrings from words that are present in s overlap, they should be wrapped together under a single pair of tags. Furthermore, if two such substrings are directly adjacent in s, their wrapping should also be merged into one continuous bold section. The desired outcome is a new version of the string s with these modifications applied where appropriate.

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 <b>'s overlap, we merge them: "<b>aaa</b><b>b</b><b>b</b><b>b</b>".
Since now the four <b>'s are consecutive, we merge them: "<b>aaabbb</b>".

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.

Approach and Intuition

To effectively add bold tags around substrings in s which are found in words while considering overlaps and adjacent positions, you can utilize the following steps:

1. Identify each substring in s that matches any string in words and record their start and end indices in s.
2. Sort these index ranges ensuring order by start index, and, if start indices are the same, by end indices (descending).
3. Initialize a merged range list and iteratively merge overlapping or adjacent ranges:
   • For each sorted index range, determine if it can be merged with the last range in the merged list (i.e., if they overlap or touch).
   • If they can be merged, update the last range in the list to encompass both.
   • Otherwise, append the new range to the list.
4. Finally, utilizing the merged index ranges, construct the resulting string:
   • Traverse through s, inserting <b> at the start of each range and </b> at the end. Adjust indices for insertion points accordingly as you modify the string length with tags.

By implementing the above algorithm, the completed string s will have substrings correctly wrapped in bold tags, ensuring that all specified conditions (overlapping and adjacency) are respected. The approach ensures an efficient traversal and merging of index ranges, avoiding excessive recomputation or unnecessary string concatenations.

Solutions

class Solution {
public:
    string encloseBold(string str, vector<string>& dict) {
        int len = str.length();
        vector<bool> isBold(len);
            
        for (string word : dict) {
            int initPos = str.find(word);
            while (initPos != -1) {
                for (int j = initPos; j < initPos + word.length(); j++) {
                    isBold[j] = true;
                }
                initPos = str.find(word, initPos + 1);
            }
        }
            
        string openTag = "<b>";
        string closeTag = "</b>";
        string result = "";
            
        for (int k = 0; k < len; k++) {
            if (isBold[k] && (k == 0 || !isBold[k - 1])) {
                result += openTag;
            }
                
            result += str[k];
                
            if (isBold[k] && (k == len - 1 || !isBold[k + 1])) {
                result += closeTag;
            }
        }
            
        return result;
    }
};