# Time:  O(n * l), n is the length of S, l is the average length of words
# Space: O(t)    , t is the size of trie

class Solution(object):
    def boldWords(self, words, S):
        """
        :type words: List[str]
        :type S: str
        :rtype: str
        """
        _trie = lambda: collections.defaultdict(_trie)
        trie = _trie()
        for i, word in enumerate(words):
            reduce(dict.__getitem__, word, trie).setdefault("_end")

        lookup = [False] * len(S)
        for i in xrange(len(S)):
            curr = trie
            k = -1
            for j in xrange(i, len(S)):
                if S[j] not in curr:
                    break
                curr = curr[S[j]]
                if "_end" in curr:
                    k = j
            for j in xrange(i, k+1):
                lookup[j] = True

        result = []
        for i in xrange(len(S)):
            if lookup[i] and (i == 0 or not lookup[i-1]):
                result.append("<b>")
            result.append(S[i])
            if lookup[i] and (i == len(S)-1 or not lookup[i+1]):
                result.append("</b>");
        return "".join(result)

@@ -1146,8 +1146,756 @@
 result)%0A
+%0A%0A# Time:  O(n * d * l), l is the average length of words%0A# Space: O(n)%0Aclass Solution2(object):%0A    def boldWords(self, words, S):%0A        %22%22%22%0A        :type words: List%5Bstr%5D%0A        :type S: str%0A        :rtype: str%0A        %22%22%22%0A        lookup = %5B0%5D * len(S)%0A        for d in words:%0A            pos = S.find(d)%0A            while pos != -1:%0A                lookup%5Bpos:pos+len(d)%5D = %5B1%5D * len(d)%0A                pos = S.find(d, pos+1)%0A%0A        result = %5B%5D%0A        for i in xrange(len(S)):%0A            if lookup%5Bi%5D and (i == 0 or not lookup%5Bi-1%5D):%0A                result.append(%22%3Cb%3E%22)%0A            result.append(S%5Bi%5D)%0A            if lookup%5Bi%5D and (i == len(S)-1 or not lookup%5Bi+1%5D):%0A                result.append(%22%3C/b%3E%22);%0A        return %22%22.join(result)%0A

Update bold-words-in-string.py