JAVA TWO Versions: (1) Boolean Array (2) Merge Interval


  • 0
    H

    Version1:
    public String addBoldTag(String s, String[] dict) {

        //Algo thinking: (1) get all the bold intervals, (2) merge
        //time = O(N^3), space = (N); N = s.length()
        
        boolean[] bold = new boolean[s.length()];
        for (String e: dict) {
            int len = e.length();
            for (int i = 0; i + len <= s.length(); i++) {
                if (s.substring(i, i + len).equals(e)) {
                    Arrays.fill(bold, i, i + len, true);
                }
            }
        }
        
        StringBuilder builder = new StringBuilder();
        char[] c = s.toCharArray();
        for (int i = 0; i < c.length; i ++) {
            if ((i == 0 && bold[i]) || (bold[i] && !bold[i - 1])) builder.append("<b>");
            builder.append(c[i]);
            if ((i == c.length - 1 && bold[i]) || ( i < c.length - 1 && bold[i] && !bold[i + 1])) builder.append("</b>");
        }
        
        return builder.toString();
    }
    

    // Version2:
    public String addBoldTag(String s, String[] dict) {

        //Algo thinking: (1) find all interval, (2) merge
        //time = O(N^3), space = O(N)
        
        if (s == null || s.length() == 0 || dict == null || dict.length == 0) return s;
        
        // step 1: find all interval
        List<Interval> list = new ArrayList<>();
        for (String e: dict) {
            int len = e.length();
            for (int i = 0; i + len <= s.length(); i++ ) {
                if (s.substring(i, i + len).equals(e)) {
                    list.add(new Interval(i, i + len));
                }
            }
        }
        
        if (list.isEmpty()) return s;
        
        // step2: merge
        Collections.sort(list, (a, b) -> a.start - b.start);
        List<Interval> merge = new ArrayList<>();
        merge.add(list.get(0));
        for (int i = 1; i < list.size(); i++) {
            Interval last = merge.get(merge.size() - 1);
            Interval curr = list.get(i);
            if (curr.start > last.end) {
                merge.add(curr);
            } else if (curr.start <= last.end && curr.end > last.end) {
                last.end = curr.end;
            }
        }
        
        int[] flag = new int[s.length() + 1];
        for (Interval inter: merge) {
            System.out.print(inter.start + ", " + inter.end);
            System.out.println();
            flag[inter.start] = 1;
            flag[inter.end] = 2;
        }
        
        //build
        StringBuilder builder = new StringBuilder();
        char[] c = s.toCharArray();
        for (int i = 0; i < c.length; i ++) {
            if (flag[i] == 1) builder.append("<b>");
            if (flag[i] == 2) builder.append("</b>");
            builder.append(c[i]);
        }
        if (flag[s.length()] == 2) builder.append("</b>");
        
        return builder.toString();
        
    }
    
    class Interval {
        int start;
        int end;
        public Interval (int s, int e) {
            start = s;
            end = e;
        }
    }

Log in to reply
 

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