Given a set of keywordswordsand a stringS, make all appearances of all keywords inSbold. 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 thatwords = ["ab", "bc"]andS = "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:

1. words has length in range [0, 50] .
2. words[i] has length in range [1, 10] .
3. S has length in range [0, 500] .
4. All characters in words[i] and S are lowercase letters.

public class Solution{
    public String boldWords(String[] words, String S) {
        boolean[] bold = new boolean[S.length() + 1];
        for (String w : words) {
            int start = S.indexOf(w, 0);
            while (start != -1) {
                Arrays.fill(bold, start, start + w.length(), true);
                start = S.indexOf(w, start + 1);
            }
        }
        StringBuilder r = new StringBuilder().append(bold[0] ? "<b>" : "");
        for (int i = 0; i < bold.length - 1; i++) {
            r.append(S.charAt(i));
            if (!bold[i] && bold[i + 1]) r.append("<b>");
            else if (bold[i] && !bold[i + 1]) r.append("</b>");
        }
        return r.toString();
    }
}