Approach #1: Brute Force [Accepted]
Let's try to learn which letters end up bold, since the resulting answer will just be the canonical one - we put bold tags around each group of bold letters.
To do this, we'll check for all occurrences of each word and mark the corresponding letters bold.
Let's work on first setting
mask[i] = true if and only if the
i-th letter is bold. For each starting position
S, for each
S[i] starts with
word, we'll set the appropriate letters bold.
Now armed with the correct
mask, let's try to output the answer. A letter in position
i is the first bold letter of the group if
mask[i] && (i == 0 || !mask[i-1]), and is the last bold letter if
mask[i] && (i == N-1 || !mask[i+1]). Alternatively, we could use
itertools.groupby in Python.
Once we know which letters are the first and last bold letters of a group, we know where to put the
Time Complexity: , where is the length of
Sand is the sum of
Space Complexity: .
Analysis written by: @awice.