Description

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:

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.

Solution

Brute-force, O(m * n ^ 2), S(n)

m: words.length
n: s.length()

原本想的比较复杂，类似显得到一组intervals，然后merge，再用StringBuilder去build result。但不知道为什么有bug。

后来发现可以用更简单的解法。在s中搜索每个word出现的index，将这些区间用boolean[] mark做标记，然后这道题就变成了找mark中的连续区间的头尾。

class Solution {
    public String boldWords(String[] words, String s) {
        int n = s.length();
        boolean[] mark = new boolean[n];
        // search each word in s, find all the matching part and mark them
        for (String word : words) { 
            int start = 0;
            while ((start = s.indexOf(word, start)) >= 0) {
                for (int i = start; i < start + word.length(); ++i) {
                    mark[i] = true;
                }
                
                ++start; // start from next position!
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            if (mark[i] && (i == 0 || !mark[i - 1])) {
                sb.append("<b>");
            }
            
            sb.append(s.charAt(i));
            
            if (mark[i] && (i == n - 1 || !mark[i + 1])) {
                sb.append("</b>");
            }
        }
        
        return sb.toString();
    }
}