# Java Solution, given a similar but easier question helps solve it

• When I saw this problem, I think it could use the same way I once used for https://leetcode.com/problems/merge-intervals/#/description, It makes this problem easy to understand.

``````class Interval{
int low;
int high;
Interval(int low, int high){
this.low = low;
this.high = high;
}
}

public class Solution {
final String left = "<b>";
final String right = "</b>";
public String addBoldTag(String s, String[] dict) {
if(dict == null || dict.length == 0){
return s;
}

int strLen = s.length();

PriorityQueue<Interval> pq = new PriorityQueue<Interval>(new Comparator<Interval>(){
public int compare(Interval i1, Interval i2){
return Integer.compare(i1.low, i2.low);
}
});

for(String sub : dict){
if(sub == null || sub.isEmpty()){
continue;
}
int len = sub.length();
int i = 0;
while(i < strLen){
int idx = s.indexOf(sub, i);
if(idx < 0){
break;
}

pq.offer(new Interval(idx, idx + len));
i = idx + 1;
}
}

int cur = 0;
int low = 0;
int high = 0;
StringBuilder sb = new StringBuilder();

while(!pq.isEmpty()){
Interval itv = pq.poll();
low = itv.low;
high = itv.high;

while(!pq.isEmpty() && pq.peek().low <= high){
high = Math.max(high, pq.poll().high);
}
sb.append(s.substring(cur, low));
sb.append(left);
sb.append(s.substring(low, high));
sb.append(right);

cur = high;
}
sb.append(s.substring(cur));

return sb.toString();
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.