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.

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

*/