Problem statement

https://binarysearch.com/problems/Embolden/

Solution

Equal to Leetcode 0616 Add Bold Tag in String.

Complexity

Time complexity is O(n * (l1 + ... + lm)), space complexity is O(n).

Code

class Solution:
    def solve(self, s, d):
        n = len(s)
        arr, ans = [0]*n, ""
        for word in d:
            T = len(word)
            for i in range(n - T + 1):
                if s[i:i+T] == word:
                    arr[i:i+T] = [1]*T

        for i in range(n):
            if arr[i] == 1 and (i == 0 or arr[i-1] == 0):
                ans += "<b>"
            ans += s[i]
            if arr[i] == 1 and (i == n-1 or arr[i+1] == 0):
                ans += "</b>"

        return ans