Leetcode 758. 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:

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.

Code (Java):

?

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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111

class Solution {     public String boldWords(String[] words, String S) {         if (words == null || words.length == 0) {             return S;         }           // step 1: find start and end pos of the substring         //         List<Interval> intervals = new ArrayList<>();         for (String t : words) {             strStr(S, t, intervals);         }                   if (intervals.isEmpty()) {             return S;         }           // step 2: sort the intervals based on the start index         //         Collections.sort(intervals, new IntervalComparator());           // step 3: merge intervals         //         List<Interval> mergedIntervals = mergeIntervals(intervals);           // step 4: compose the result based on the merged intervals         //         StringBuilder sb = new StringBuilder();         int prev = 0;                   for (int i = 0; i < mergedIntervals.size(); i++) {             Interval curr = mergedIntervals.get(i);             // prev seg             //             sb.append(S.substring(prev, curr.start));             sb.append("<b>");                           // curr seg             //             sb.append(S.substring(curr.start, curr.end + 1));             sb.append("</b>");                           prev = curr.end + 1;         }                   // trailing substring         //         if (prev < S.length()) {             sb.append(S.substring(prev));         }           return sb.toString();     }       private void strStr(String s, String t, List<Interval> list) {         for (int i = 0; i < s.length() - t.length() + 1; i++) {             int j = 0;             while (j < t.length()) {                 if (s.charAt(i + j) == t.charAt(j)) {                     j++;                 } else {                     break;                 }             }               if (j == t.length()) {                 Interval interval = new Interval(i, i + j - 1);                 list.add(interval);             }         }     }       private List<Interval> mergeIntervals(List<Interval> intervals) {         List<Interval> ans = new ArrayList<>();                   if (intervals == null || intervals.isEmpty()) {             return ans;         }           Interval prev = intervals.get(0);         for (int i = 1; i < intervals.size(); i++) {             Interval curr = intervals.get(i);             if (prev.end >= curr.start || prev.end + 1 == curr.start) {                 prev.end = Math.max(prev.end, curr.end);             } else {                 ans.add(new Interval(prev.start, prev.end));                 prev = curr;             }         }           ans.add(prev);           return ans;     } }   class Interval {         int start;         int end;           public Interval(int s, int e) {             start = s;             end = e;         }     }   class IntervalComparator implements Comparator<Interval> {     public int compare(Interval a, Interval b) {         return a.start - b.start;     } }