616. Add Bold Tag in String

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.

Solution

The first idea is to arrange the range that shall be bold.

It will be similar to an interval merge problem. My personal preference is to use a treeMap.

Using floorKey to get the prevStart of the interval and the nextStart of the next interval.

With some merge operations, we can have a treeMap to record all the ranges.

And we iterate the original string and append <b> (in the start of interval ) or </b> (in the end of interval) accordingly.

    public String addBoldTag(String s, String[] words) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int i = 0; i < s.length(); i++){
            for(String word : words) {
                if(s.substring(i).startsWith(word)) {
                    update(map, i, i + word.length()-1);
                }
            }    
        }
        
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            if(map.keySet().contains(i)){
                ret.append("<b>");
            }
            ret.append(s.charAt(i));
            if(map.values().contains(i)){
                ret.append("</b>");
            }
            
        }     
        return ret.toString();
    }
    
    public void update(TreeMap<Integer, Integer> map, int start, int end) {
        Integer prevStart = map.floorKey(start);
        int prevEnd = prevStart == null ? -1 : map.get(prevStart);
        Integer nextStart = map.floorKey(end);
        int nextEnd = nextStart == null ? -1 : map.get(nextStart);
        
        if(start != 0 && prevEnd >= (start-1)){
            start = prevStart;
        }
        if(nextEnd > end){
            end = nextEnd;
        }
        
        map.put(start, end);
        map.subMap(start, false, end, true).clear();
    }