[LintCode] Problem 812 - Bold Words in String

Posted on | In ,

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.

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.

Example

No.1

Input:
[“ab”, “bc”]
“aabcd”

Output:
“a<b>abc</b>d”

Explanation:
Note that returning “a<b>a<b>b</b>c</b>d” would use more tags, so it is incorrect.

No.2

Input:
[“bcccaeb”,”b”,”eedcbda”,”aeebebebd”,”ccd”,”eabbbdcde”,”deaaea”,”aea”,”accebbb”,”d”]
“ceaaabbbedabbecbcced”

Output:
“ceaaa<b>bbb</b>e<b>d</b>a<b>bb</b>ec<b>b</b>cce<b>d</b>“

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public String boldWords(String[] words, String S) {
    StringBuilder sb = new StringBuilder();
    int n = S.length();
    int[] array = new int[n + 1];
    int sum = 0;
    int preSum = 0;

    for (String word : words) {
        int idx = 0;

        while ((idx = S.indexOf(word, idx)) >= 0) {
            array[idx]++;
            array[idx + word.length()]--;
            idx++;
        }
    }

    for (int i = 0; i <= n; i++) {
        sum += array[i];

        if (sum > 0 && preSum == 0)
            sb.append("<b>");
        else if (sum == 0 && preSum > 0)
            sb.append("</b>");
        
        if (i < n)
            sb.append(S.charAt(i));

        preSum = sum;
    }

    return sb.toString();
}