616. Add Bold Tag in String

class Solution {
    TrieNode root;
    public String addBoldTag(String s, String[] dict) {
        root = new TrieNode('a');
        for (String word : dict) {
            addToTrie(root, word);
        }
        int pt = 0;
        List intervals = new ArrayList<>();
        while (pt < s.length()) {
            int reach = getReachLength(root, s, pt);
            if (reach != 0) {
                intervals.add(new Interval(pt, pt + reach - 1));
            }
            pt++;
        }
        intervals = mergeIntervals(intervals);
        int prev = 0;
        StringBuilder sb = new StringBuilder();
        for (Interval interval : intervals) {
            sb.append(s.substring(prev, interval.start));
            sb.append("");
            sb.append(s.substring(interval.start, interval.end + 1));
            sb.append("");
            prev = interval.end + 1;
        }
        sb.append(s.substring(prev));
        return sb.toString();
    }
    
    private List mergeIntervals(List intervals) {
        List ans = new ArrayList<>();
        if (intervals == null) return ans;
        
        Interval last = null;
        for (Interval cur : intervals) {
            if (last == null) {
                last = cur;
                continue;
            }
            if (cur.start <= last.end + 1) {
                last.end = Math.max(last.end, cur.end);
            } else {
                ans.add(last);
                last = cur;
            }
        }
        if (last != null) ans.add(last);
        return ans;
    }
    private void addToTrie(TrieNode root, String word) {
        for (int i = 0; i < word.length(); i++) {
            root = root.getOrAdd(word.charAt(i));
        }
        root.isWord = true;
    }
    private int getReachLength(TrieNode root, String s, int pt) {
        List ans = new ArrayList<>();
        int i = 0;
        while (root != null && pt + i < s.length()) {
            char c = s.charAt(pt + i);
            root = root.getChild(c);
            if (root!= null && root.isWord) ans.add(i + 1);
            i++;
        }
        if (ans.size() == 0) return 0;
        return ans.get(ans.size() - 1);
    }
}
class Interval {
    int start;
    int end;
    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}
class TrieNode {
    char ch;
    boolean isWord;
    Map children;
    public TrieNode(char ch) {
        this.ch = ch;
        this.children = new HashMap<>();
    }
    public TrieNode getOrAdd(char c) {
        children.putIfAbsent(c, new TrieNode(c));
        return children.get(c);
    }
    public TrieNode getChild(char c) {
        return children.get(c);
    }
}