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).