Python short merge interval solution


  • 0
    Y
    class Solution(object):
        def addBoldTag(self, s, dict):
            """
            :type s: str
            :type dict: List[str]
            :rtype: str
            """
            #find all overlapping matches
            matches = []
            for word in dict:
                start = 0
                while True:
                    start = s.find(word, start)
                    if start == -1:
                        break
                    else:
                        matches.append([start, start + len(word)])
                        start += 1
            #merge all matches like intervals            
            matches = sorted(matches)
            self.mergeInterval(matches)
            #concatenate string
            ret = ""
            pos = 0
            for start, end in matches:
                ret += s[pos:start] + '<b>' + s[start:end] + '</b>'
                pos = end
            ret += s[pos:]
            return ret
        
        def mergeInterval(self, intervals):
            start, end = 0, 0
            n = len(intervals)
            while end < n:
                intervals[start] = intervals[end]
                while end < n and intervals[end][0] <= intervals[start][1]:
                    intervals[start][1] = max(intervals[start][1], intervals[end][1])
                    end += 1
                start += 1
            del intervals[start:]
    

  • 0
    P

    Same thoughts, using regex and merging intervals. But my code is very slow ... T.T

    import re
    class Solution(object):
        def addBoldTag(self, s, dict):
            """
            :type s: str
            :type dict: List[str]
            :rtype: str
            """
            stack = []
            for pat in dict:
            	for match in re.finditer("(?={})".format(pat), s):
            		stack.append( [match.start(), match.start()+len(pat)] )
            stack.sort()
            mstack = []
            for i, (start, end) in enumerate(stack):
            	if i == 0 or start > mstack[-1][1]:
            		mstack.append( [start, end] )
            	else:
            		mstack[-1][1] = max(end, mstack[-1][1])
            for start, end in mstack[::-1]:
            	s = s[:start] + '<b>' + s[start:end] + '</b>' + s[end:]
            return s
    

Log in to reply
 

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