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

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;
    }
}