# Java solution, similar to merge interval

• ``````class Solution {
public String addBoldTag(String s, String[] dict) {
// algorithm 2017/09/04: this is a merge-interval problem,
// as we can check each dictionary and find the interval where the match occurs, and then merge them
// example: s = "aaabbcc", dict = ["aaa","aab","bc"]
// "aaa' => [0,2], "aab" => [1,3], "bc" => [4,5]
// they are merged into [0,5]
if (null == s) {
return s;
}
if (0 == s.length()) {
return s;
}
if (null == dict || 0 == dict.length) {
return s;
}

List<int[]> listIntervals = new ArrayList<>();
for (String word : dict) {
findOccurrences(s, word, listIntervals);
}

if (listIntervals.isEmpty()) {
return s;   // no match anywhere
}

// sort intervals by start, for each merge
Collections.sort(listIntervals, new Comparator<int[]>() {
public int compare(int[] interval1, int[] interval2) {
return interval1[0] - interval2[0];
}
});

// find openMarks and closeMarks by merging intervals

// now listIntervals contains non-overlapping intervals; converting them into a 1D array
List<Integer> openMarks  = new ArrayList<>();
List<Integer> closeMarks = new ArrayList<>();

int currentOpenMark    = listIntervals.get(0)[0];
int potentialCloseMark = listIntervals.get(0)[1];

int countIntervals     = listIntervals.size();
for (int index = 1; index < countIntervals; index++) {
int nextOpenMark   = listIntervals.get(index)[0];
int nextCloseMark  = listIntervals.get(index)[1];
if (nextOpenMark <= potentialCloseMark+1) {
potentialCloseMark = Math.max(potentialCloseMark, nextCloseMark);
} else {

currentOpenMark    = nextOpenMark;
potentialCloseMark = nextCloseMark;
}
}
// the last one is never added - put it

StringBuilder builder = new StringBuilder();
int countMarks        = openMarks.size();
int strLen            = s.length();
int currentMark       = 0;
for (int index = 0; index < strLen; index++) {
char ch = s.charAt(index);
// openMark and closeMark might be on the same index
if (currentMark < countMarks) {
if (index == openMarks.get(currentMark) && index == closeMarks.get(currentMark)) {
builder.append("<b>");
builder.append(ch);
builder.append("</b>");
currentMark++;      // move to next mark
assert currentMark <= countMarks;
} else if (index == openMarks.get(currentMark)) {
builder.append("<b>");
builder.append(ch);
} else if (index == closeMarks.get(currentMark)) {
builder.append(ch);
builder.append("</b>");
currentMark++;      // move to next mark
assert currentMark <= countMarks;
} else {
builder.append(ch);
}
} else {
builder.append(ch);
}
}

return builder.toString();
}

private void findOccurrences(String str, String word, List<int[]> listIntervals) {
assert null != str && 0 < str.length() && null != word && 0 < word.length();

int wordLen       = word.length();
int strLen        = str.length();
int indexStart    = 0;
while (indexStart < strLen) {
int indexOccurred = str.indexOf(word, indexStart);
if (-1 == indexOccurred) {
return;
} else {
listIntervals.add(new int[]{indexOccurred, indexOccurred + wordLen - 1});
}
indexStart = indexOccurred + 1;     // make sure we do not move to indexOccurred + wordLen
// reason: we want to cover the case: "yzzz" with dictionary "yz" + "zz"
}
}
}``````

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