616. Add Bold Tag in String

Version #1 Merge Intervals

13.51 %
class Solution {
    public String addBoldTag(String s, String[] dict) {
// [interval[0], interval[1])
List<int[]> intervals = new ArrayList<>();
for (String word : dict) {
int start = 0;
while (start >= 0) {
start = s.indexOf(word, start);
if (start == -1) {
break;
}
intervals.add(new int[]{start, start + word.length()});
start++;
}
}
Collections.sort(intervals, Comparator.comparing(a -> a[0])); // only compare the start index
int i = 0;
List<int[]> merged = new ArrayList<>();
while (i < intervals.size()) {
int[] curr = intervals.get(i);
while (i < intervals.size() - 1 && intervals.get(i + 1)[0] <= curr[1]) {
curr[1] = Math.max(curr[1], intervals.get(i + 1)[1]);
i++;
}
merged.add(curr);
i++;
}
StringBuilder sb = new StringBuilder();
int prev = 0;
for (int[] interval : merged) {
sb.append(s.substring(prev, interval[0])).append("<b>").append(s.substring(interval[0], interval[1])).append("</b>");
prev = interval[1];
}
sb.append(s.substring(prev));
return sb.toString();
}
}