Problem statement

https://leetcode.com/problems/add-bold-tag-in-string/

Solution

Let n be length of s, m is number of strings in dictionary and l1, ... , lm their lengths. Let us use binary list of length n with indication if we need to bold this symbol or not.

First approach: for each word in dictionary and for every place check if we have found it.

Complexity

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

Code

class Solution:
    def addBoldTag(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

Remark

Another approach is to use KMP or Rabin-Karp to find in O(n) for each word its occurrences in s. Time complexity is O(nm), space is O(n).

Finally, we can use Tries: we create it from all words in dictionary and then for each letter in s try to find it in Trie, and if we found it, change some bits of our binary list to one. Space complexity is O(n + (l1 + ... + lm)), time complexity is O(n * max(l1, ..., lm). This is the best theoretical complexity approach in majority cases.