Python beat 100%


  • 0
    W
    class Solution(object):
        def addBoldTag(self, s, dict):
            """
            :type s: str
            :type dict: List[str]
            :rtype: str
            """
            # step 1: find the start/stop index of each word
            ij=[]
            for word in dict:
                i=0
                while True: # find overlap match
                    tmp=s[i:].find(word)
                    if tmp==-1: break
                    i+=tmp
                    j=i+len(word)
                    ij.append((i,j))
                    i+=1
            if not ij: return s
    
            # step 2: combine the range with overlap
            ij.sort()
            ij_combine=[]
            i,j=ij[0]
            for k in range(1,len(ij)):
                if ij[k][0]<=j:
                    j=max(j,ij[k][1])
                else:
                    ij_combine.append((i,j))
                    i,j=ij[k]
            ij_combine.append((i,j))
    
            # step 3: insert <b> and </b>
            res=list(s)
            for k,(i,j) in enumerate(ij_combine):
                res.insert(i+k*2,'<b>')
                res.insert(j+k*2+1,'</b>')
            return ''.join(res)

Log in to reply
 

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