Bold Words In String - Leetcode Solution

Problem Statement:

Given a string s and a list of strings dict, you need to add a closed pair of bold tag <b> and </b> to wrap the substrings in s that exist in dict. If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.

Example 1:

Input: s = "abcxyz123" dict = ["abc","123"] Output: "<b>abc</b>xyz<b>123</b>" Example 2:

Input: s = "aaabbcc" dict = ["aaa","aab","bc"] Output: "<b>aaa</b>bb<b>c</b>c"

Solution:

The problem seems quite simple to solve using a greedy approach. We can iterate through the string, and for each index i, we can check if any of the words in the dictionary starts at i. If it does, we can add a "<b>" before the word and "</b>" after it. We can then continue scanning the string for the next word in the dictionary that starts after the current word.

If two such substrings overlap, we need to wrap them together by only one pair of closed bold tags. We can do this by keeping track of the end index of the previous word we wrapped in bold tags. If the current word starts before the end of the previous word, we can update the end index of the previous word to be the end index of the current word.

Also, if two substrings wrapped by bold tags are consecutive, we need to combine them. We can do this by keeping track of the start index and end index of the previous bold substring. If the current bold substring starts at the end index of the previous bold substring, we can combine them by updating the end index of the previous bold substring to be the end index of the current bold substring.

We can implement this approach using a stack to keep track of the start and end indices of the bold substrings we have wrapped so far. Here is the Python code for the same:

class Solution:
    def addBoldTag(self, s: str, dict: List[str]) -> str:
        stack = []
        for i in range(len(s)):
            max_end = -1
            for word in dict:
                if s.startswith(word, i):
                    max_end = max(max_end, i + len(word))
            if max_end > -1:
                if not stack or i > stack[-1][1]:
                    stack.append([i, max_end])
                else:
                    stack[-1][1] = max(stack[-1][1], max_end)
        
        res = []
        i = 0
        for start, end in stack:
            res.append(s[i:start])
            res.append("<b>" + s[start:end] + "</b>")
            i = end
        res.append(s[i:])
        return "".join(res)

Time Complexity: O(n*d), where d is the average length of the words in the dictionary.

Space Complexity: O(n), where n is the length of the input string.

1