> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0616-add-bold-tag-in-string.md).

# 0616. Add Bold Tag in String

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

## Description

You are given a string `s` and an array of strings `words`. You should add a closed pair of bold tag `<b>` and `</b>` to wrap the substrings in `s` that exist in `words`. If two such substrings overlap, you should wrap them together with only one pair of closed bold-tag. If two substrings wrapped by bold tags are consecutive, you should combine them.

Return `s` *after adding the bold tags*.

**Example 1:**

```
**Input:** s = "abcxyz123", words = ["abc","123"]
**Output:** "<b>abc</b>xyz<b>123</b>"
```

**Example 2:**

```
**Input:** s = "aaabbcc", words = ["aaa","aab","bc"]
**Output:** "<b>aaabbc</b>c"
```

**Constraints:**

* `1 <= s.length <= 1000`
* `0 <= words.length <= 100`
* `1 <= words[i].length <= 1000`
* `s` and `words[i]` consist of English letters and digits.
* All the values of `words` are **unique**.

**Note:** This question is the same as 758: <https://leetcode.com/problems/bold-words-in-string/>

## ac

The key is `cover[i]`, sometimes you may use substring to compare with dict, sometimes you may do the other way round, use the dict to search in String.

```java
class Solution {
    public String addBoldTag(String s, String[] dict) {
        // edge cases
        if (s == null || s.length() == 0 || dict == null || dict.length == 0) return s;

        // which letter is covered?
        boolean[] cover = new boolean[s.length()];
        for (int i = 0; i < s.length(); i++) {
            int len = 0;
            for (String w : dict) {
                if (s.startsWith(w, i)) {
                    len = Math.max(len, w.length());
                }
            }
            Arrays.fill(cover, i, i+len, true);
        }

        // find those covered letters
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < cover.length; i++) {
            if (!cover[i]) {
               sb.append(s.charAt(i)); 
            } else {
                int j = i;
                while (j < cover.length && cover[j]) j++;
                sb.append("<b>" + s.substring(i, j) + "</b>");
                i = j-1;
            }
        }

        // res
        return sb.toString();
    }
}
/*
boolean[] cover, determine word break.
iterate through index, find longest word, cover[i] = true
find all those cover[i] == true

*/
```