616 Add Bold Tag in String

Given a string s and a list of strings dict, you need to add a closed pair of bold tag <b> and </b> to wrap the substrings in s that exist in dict. If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.

Example 1:

Input: 
s = "abcxyz123"
dict = ["abc","123"]
Output:
"<b>abc</b>xyz<b>123</b>"

Example 2:

Input: 
s = "aaabbcc"
dict = ["aaa","aab","bc"]
Output:
"<b>aaabbc</b>c"

Note:

1. The given dict won't contain duplicates, and its length won't exceed 100.

2. All the strings in input have length in range [1, 1000].

The Idea: Although I have not approached the problem in the same way, this problem is identical to merge intervals. Each substring that is in the dictionary creates an interval in s. Each interval has a start and end point, and this problem can be reduced to merging all these intervals together and inserting a <b> and </b> tag at the start and end of each interval respectfully.

The approach I took included a boolean array. For each word in the dictionary that exists in the substring s, we mark it as active in the boolean array. A trie also works for this. The boolean array will naturally merge intervals on its own. Then in the final step, append opening and closing tags at the start and end of each active interval.

Complexity: O(n*m) time where n is the size of s and m is the number of words in the dictionary. O(|S|) space

class Solution:
    def addBoldTag(self, s, dict):
        """
        :type s: str
        :type dict: List[str]
        :rtype: str
        """

        intervals = [False] * len(s)
        for i in range(0, len(s)):
            for word in dict:
                if s.startswith(word, i):
                    intervals[i:i + len(word)] = [True] * len(word)

        final_str = []
        bold_active = False
        for i, bold in enumerate(intervals):
            # start of bold
            if bold and not bold_active:
                final_str.append('<b>')
                bold_active = True
            # end of bold
            elif not bold and bold_active:
                final_str.append('</b>')
                bold_active = False
            final_str.append(s[i])

        if intervals[-1]:
            final_str.append('</b>')

        return ''.join(final_str)


obj = Solution()
print(obj.addBoldTag("abcxyz123", ["abc", "123"]))  # "<b>abc</b>xyz<b>123</b>"
print(obj.addBoldTag("aaabbcc", ["aaa","aab","bc"]))  # "<b>aaabbc</b>c"