[LeetCode] 616. Add Bold Tag in String

 String과 words List가 input으로 주어지고, 주어진 words List의 substring이 s에 존재한다면 html의 bold tag(<b></b>)를 앞뒤로 씌워 return 하는 문제다.

 

Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"
Explanation: The two strings of words are substrings of s as following: "abcxyz123".
We add <b> before each substring and </b> after each substring.

 

 이 문제 역시 다양한 Data Structure와 Algorithm을 활용해 풀 수 있겠지만, Min Heap을 사용해 풀었다. Min Heap은 일치하는 substring의 leftmost와 rightmost를 element로 가지고 leftmost를 기준으로 형성했다. Min Heap을 사용한 이유는 Min Heap에 담겨진 element 간에 겹쳐지는 구간이 발생한다면 그 구간은 통합해 한 개의 bold tage로 씌울 수 있기 때문이다.

class Solution:
    def addBoldTag(self, s: str, words: List[str]) -> str:
        h = []
        
        for i in range(len(s)):
            for j in range(len(words)):
                l = len(words[j])
                if s[i:i+l] == words[j]:
                    heapq.heappush(h, [i, i+l-1])

        if len(h) == 0:
            return s

        p = []
        c = heapq.heappop(h)
        l, r = c[0], c[1]
        for i in range(len(h)):
            c = heapq.heappop(h)
            if r >= c[0]-1:
                r = max(r, c[1])
            else:
                p.append([l, r])
                l, r = c[0], c[1]
        p.append([l, r])
        
        padding = 0
        for i, item in enumerate(p):
            s = s[:item[0]+padding] + '<b>' + s[item[0]+padding:item[1]+1+padding] + '</b>' + s[item[1]+1+padding:]
            padding += 7

        return s