Code Implementation

class Solution:
    def addBoldTag(self, s: str, words: List[str]) -> str:
        n = len(s)
        bold = [False] * n
        for word in words:
            start = s.find(word)
            while start != -1:
                for i in range(start, start + len(word)):
                    bold[i] = True
                start = s.find(word, start + 1)
        res = []
        i = 0
        while i < n:
            if bold[i]:
                res.append("<b>")
                while i < n and bold[i]:
                    res.append(s[i])
                    i += 1
                res.append("</b>")
            else:
                res.append(s[i])
                i += 1
        return "".join(res)
      

class Solution {
public:
    string addBoldTag(string s, vector<string>& words) {
        int n = s.size();
        vector<bool> bold(n, false);
        for (const string& word : words) {
            size_t pos = s.find(word);
            while (pos != string::npos) {
                for (int i = pos; i < pos + word.size(); ++i)
                    bold[i] = true;
                pos = s.find(word, pos + 1);
            }
        }
        string res;
        int i = 0;
        while (i < n) {
            if (bold[i]) {
                res += "<b>";
                while (i < n && bold[i]) {
                    res += s[i];
                    ++i;
                }
                res += "</b>";
            } else {
                res += s[i++];
            }
        }
        return res;
    }
};
      

class Solution {
    public String addBoldTag(String s, String[] words) {
        int n = s.length();
        boolean[] bold = new boolean[n];
        for (String word : words) {
            int start = s.indexOf(word);
            while (start != -1) {
                for (int i = start; i < start + word.length(); i++) {
                    bold[i] = true;
                }
                start = s.indexOf(word, start + 1);
            }
        }
        StringBuilder res = new StringBuilder();
        int i = 0;
        while (i < n) {
            if (bold[i]) {
                res.append("<b>");
                while (i < n && bold[i]) {
                    res.append(s.charAt(i));
                    i++;
                }
                res.append("</b>");
            } else {
                res.append(s.charAt(i));
                i++;
            }
        }
        return res.toString();
    }
}
      

var addBoldTag = function(s, words) {
    const n = s.length;
    const bold = Array(n).fill(false);
    for (const word of words) {
        let start = s.indexOf(word);
        while (start !== -1) {
            for (let i = start; i < start + word.length; i++) {
                bold[i] = true;
            }
            start = s.indexOf(word, start + 1);
        }
    }
    let res = '';
    let i = 0;
    while (i < n) {
        if (bold[i]) {
            res += '<b>';
            while (i < n && bold[i]) {
                res += s[i];
                i++;
            }
            res += '</b>';
        } else {
            res += s[i];
            i++;
        }
    }
    return res;
};
      

Problem Description

Given a string s and an array of strings words, you need to wrap all substrings in s that match any word in words with a bold HTML tag: <b>...</b>. If two or more matching substrings overlap or are adjacent, you should wrap them together with a single pair of bold tags. The output should be the resulting string with the appropriate bold tags inserted.

• Each word in words can be used multiple times, as long as it matches a substring in s.
• The solution must merge overlapping and adjacent bold ranges.
• Return the final string after inserting the bold tags.

Thought Process

The first idea that comes to mind is to look for every occurrence of each word in words within the string s, and for each match, insert <b> and </b> around it. However, this approach quickly becomes tricky because inserting tags changes the string's indices, making further searches unreliable.

Also, since matches can overlap or touch each other, inserting tags immediately might result in nested or redundant tags. Therefore, we need a way to mark which characters in s should be bolded, and then do a single pass to insert tags at the correct places, merging overlapping or adjacent ranges.

To optimize, instead of repeatedly modifying the string, we can use an auxiliary array to track which characters should be bold, and then construct the final string in one go.

Solution Approach

• Step 1: Mark Bold Positions
  Create a boolean array bold of the same length as s. For each word in words, search for all occurrences in s. For each match, mark the corresponding positions in bold as True.
• Step 2: Merge Bold Ranges
  The bold array now represents which characters need to be wrapped in a bold tag. Adjacent or overlapping matches will have consecutive True values.
• Step 3: Build the Output String
  Traverse s with the bold array. When entering a bold region (i.e., bold[i] is True and i == 0 or bold[i-1] is False), insert <b>. When leaving a bold region (i.e., bold[i] is True and i == n-1 or bold[i+1] is False), insert </b>.
• Step 4: Return the Result
  Join the constructed characters and tags into the final string.

This approach ensures we only scan the string a couple of times, and merging of bold regions is handled naturally by the bold array.

Example Walkthrough

Input: s = "abcxyz123", words = ["abc","123"]

1. Mark bold positions:
   - "abc" is found at index 0. Mark bold[0], bold[1], bold[2] as True.
   - "123" is found at index 6. Mark bold[6], bold[7], bold[8] as True.
   The bold array is now: [True, True, True, False, False, False, True, True, True]
2. Build output string:
   - At index 0, start of a bold region: insert <b>
   - Output "abc"
   - At index 3, end of bold region: insert </b>
   - Output "xyz"
   - At index 6, start of a bold region: insert <b>
   - Output "123"
   - At index 9, end of bold region: insert </b>
3. Final output: <b>abc</b>xyz<b>123</b>

Time and Space Complexity

• Brute-force approach:
  For each index, try every word at every position, potentially leading to O(N * M * L) time, where N is the length of s, M is the number of words, and L is the average word length.
• Optimized approach:
  - Marking bold regions: For each word, we scan s to find all occurrences. This is O(N * M * L) in the worst case.
  - Building the result: Single pass through s, O(N).
  - Space: O(N) for the bold array and output string.
• Note: For a large dictionary, a Trie could be used to speed up matching, but for most constraints, this direct approach suffices.

Summary

The solution marks all characters in s that need to be bold using a boolean array, then constructs the output by inserting bold tags only at the boundaries of these regions. This avoids the pitfalls of modifying the string in place and elegantly handles overlapping or adjacent matches. The approach is straightforward, efficient for typical constraints, and easy to understand.