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"

这道题是一个带了一丝伪装的扫描线merge interval问题，但是从题目的描述来说就能比较明确的意识到，尤其是第二个例子，确定是一个扫描线问题之后，首先就要找到扫描线需要的区间输入，这里也可以比较清楚的看出来其实就是在s字符串里面寻找dict里的所有词可能出现的位置，所以首先要做的就是对字符串s进行查找并将查找的结果以起始点的方式放入intervals数组中然后进行排序，再利用扫描线对里面的区间统一处理，这里的小技巧是利用了一个count的变量来记录当前有几层重叠，如果当前点是起点则count加一表示多了两个词重叠，如果终点则count减一，这样就能得到正确结果了

def comparator(A, B):
    if A[0] != B[0]:
        return A[0] - B[0]
    if A[1] == True:
        return -1
    elif B[1] == True:
        return 1
    else:
        return 0

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

        for word in dict:
            tmp = s.find(word)
            length = len(word)
            while tmp != -1:
                intervals.append([tmp, True])
                intervals.append([tmp + length, False])                   # 终点位置要比结束的位置往前推一格
                tmp = s.find(word, tmp + 1)

        intervals.sort(cmp=comparator)

        count = 0
        cur = 0
        res = ''
        for interval in intervals:
            if interval[1]:
                if count == 0:
                    res += s[cur : interval[0]]
                    cur = interval[0]
                count += 1
            else:
                count -= 1
                if count == 0:
                    res += ('<b>' + s[cur : interval[0]] + '</b>')
                    cur = interval[0]

        return res + s[cur : ]