Python, Straightforward with Explanation


  • 2

    We put all the words in our given wordlist into a trie. Then, let's paint any letter in our string that should be bolded. For every starting position i in our string, let's find the longest word that S[i:] starts with, and paint S[i:i+len(word)].

    Afterwards, we have a boolean array where paint[i] = True iff S[i] is bolded. Let's write our letters from left to right. If we are on a bolded letter and there is an unbolded letter to the left (or if we are at the leftmost letter), we should start a <b> tag. Similarly for </b> tags: they start when our bolded letter has an unbolded right neighbor (or we are at the right-most letter.)

    def addBoldTag(self, S, A):
        END = False
        _trie = lambda: collections.defaultdict(_trie)
        trie = _trie()
        
        for word in A:
            cur = trie
            for letter in word:
                cur = cur[letter]
            cur[END] = END
        
        paint = [False] * len(S)
        for i in xrange(len(S)):
            cur = trie
            end = i
            for j in xrange(i, len(S)):
                if S[j] not in cur: break
                cur = cur[S[j]]
                if END in cur:
                    end = j + 1
            paint[i:end] = [True] * (end - i)
        
        ans = []
        for i, u in enumerate(S):
            if paint[i] and (i == 0 or not paint[i-1]):
                ans.append('<b>')
            ans.append(u)
            if paint[i] and (i == len(S) - 1 or not paint[i+1]):
                ans.append('</b>')
            
        return "".join(ans)
    

    Alternatively, for a simpler but slower idea, we could check if each word starts at each position.

    def addBoldTag(self, S, A): 
        paint = [False] * len(S)
        for i in xrange(len(S)):
            block = S[i:]
            for word in A:
                if block.startswith(word):
                    paint[i:i+len(word)] = [True] * len(word)
    
        ans = []
        for i, u in enumerate(S):
            if paint[i] and (i == 0 or not paint[i-1]):
                ans.append('<b>')
            ans.append(u)
            if paint[i] and (i == len(S) - 1 or not paint[i+1]):
                ans.append('</b>')
            
        return "".join(ans)
    

  • 1

    Cool solution but it takes 460ms. The slower idea runs even faster (260ms).


  • 0
    Z

    Good idea! You may be able to get an O(n) solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.