LeetCode 616. Add Bold Tag in String

Question

You are given a string s and an array of strings words. You should add a closed pair of bold tag <b> and </b> to wrap the substrings in s that exist in words. If two such substrings overlap, you should wrap them together with only one pair of closed bold-tag. If two substrings wrapped by bold tags are consecutive, you should combine them.

Return s after adding the bold tags.

Example 1:

Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"

Example 2:

Input: s = "aaabbcc", words = ["aaa","aab","bc"]
Output: "<b>aaabbc</b>c"

Constraints:

• 1 <= s.length <= 1000
• 0 <= words.length <= 100
• 1 <= words[i].length <= 1000
• s and words[i] consist of English letters and digits.
• All the values of words are unique.

Source: https://leetcode.com/problems/add-bold-tag-in-string/

Solution

Convert this problem to a merge interval problem.

class Interval {
    public int start; // inclusive
    public int end; // exclusive

    public Interval(int s, int e) {
        this.start = s;
        this.end = e;
    }
}

private List<Interval> mergeIntervals(List<Interval> intervals) {
    if (intervals == null || intervals.size() == 0) {
        return new LinkedList<Interval>();
    }
    // sort intervals by start in ascending order
    Collections.sort(intervals, new Comparator<Interval>() {
        @Override
        public int compare(Interval o1, Interval o2) {
            return o1.start - o2.start;
        }
    });
    LinkedList<Interval> merged = new LinkedList<>();
    int size = intervals.size();
    merged.add(intervals.get(0));
    for (int i = 1; i < size; i++) {
        Interval curr = intervals.get(i);
        Interval last = merged.getLast();
        if (curr.start > last.end) { // no overlap
            merged.add(curr);
        } else {
            last.end = Math.max(last.end, curr.end);
        }
    }
    return merged;
}

public String addBoldTag(String s, String[] words) {
    List<Interval> intervals = new ArrayList<>();
    for (String pattern : words) {
        int plen = pattern.length();
        int index = s.indexOf(pattern, -1);
        while (index != -1) {
            intervals.add(new Interval(index, index + plen));
            index = s.indexOf(pattern, index + 1);
        }
    }
    List<Interval> merged = mergeIntervals(intervals);
    StringBuilder builder = new StringBuilder();
    int prevEnd = 0;
    for (Interval interval : merged) {
        builder.append(s.substring(prevEnd, interval.start));
        builder.append("<b>");
        builder.append(s.substring(interval.start, interval.end));
        builder.append("</b>");
        prevEnd = interval.end;
    }
    builder.append(s.substring(prevEnd, s.length()));
    return builder.toString();
}