Java solution, similar to merge interval


  • 0
    A
    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 {
                    openMarks.add(currentOpenMark);
                    closeMarks.add(potentialCloseMark);
    
                    currentOpenMark    = nextOpenMark;
                    potentialCloseMark = nextCloseMark;
                }
            }
            // the last one is never added - put it
            openMarks.add(currentOpenMark);
            closeMarks.add(potentialCloseMark);
    
            // add bold tag now
    
            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"
            }
        }
    }

Log in to reply
 

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