# Bold Words in String

<https://leetcode.com/contest/weekly-contest-66/problems/bold-words-in-string/>

> Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between \<b> and \</b> tags become bold.
>
> The returned string should use the least number of tags possible, and of course the tags should form a valid combination.
>
> For example, given that words = \["ab", "bc"] and S = "aabcd", we should return "a\<b>abc\</b>d". Note that returning "a\<b>a\<b>b\</b>c\</b>d" would use more tags, so it is incorrect.
>
> Note:
>
> words has length in range \[0, 50].
>
> words\[i] has length in range \[1, 10].
>
> S has length in range \[0, 500].
>
> All characters in words\[i] and S are lowercase letters.

## Thoughts

最开始想了个过于复杂的方法. 因为要求tag数目最少, 也就是要把有overlap的合并, 因此想到用merge intersection的方法做. 但这么做过于复杂了. 还可以把出现了的都标记.

## Code

```
class Solution {
    public String boldWords(String[] words, String S) {
        int n = S.length();
        boolean[] mark = new boolean[n];
        for (String word : words) {
            for (int i = 0; i <= n - word.length(); i++) {
                if (S.substring(i, i + word.length()).equals(word)) {
                    for (int j = i; j < i + word.length(); j++) {
                        mark[j] = true;
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (mark[i] && (i == 0 || !mark[i - 1])) {
                sb.append("<b>");
            } 
            if (i > 0 && !mark[i] && mark[i - 1]) {
                sb.append("</b>");
            }
            sb.append(S.charAt(i));
        }
        if (mark[n - 1]) {
            sb.append("</b>");
        }
        return sb.toString();
    }
}
```

## Analysis

时间复杂度O(N^2).
