Problem statement

https://leetcode.com/problems/bold-words-in-string/

Solution

This problem is exactly the same as 0616 Add Bold Tag in String. First approach: for each word in dictionary and for every place check if we have found it.

Complexity

Time complexity is $O(n\cdot \sum\limits_{i=1}^n l_m)$, space complexity is $O(n)$.

Code

class Solution:
    def boldWords(self, d, s):
        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