Java Solution, given a similar but easier question helps solve it


  • 0

    When I saw this problem, I think it could use the same way I once used for https://leetcode.com/problems/merge-intervals/#/description, It makes this problem easy to understand.

    class Interval{
        int low;
        int high;
        Interval(int low, int high){
            this.low = low;
            this.high = high;
        }
    }
    
    public class Solution {
        final String left = "<b>";
        final String right = "</b>";
        public String addBoldTag(String s, String[] dict) {
            if(dict == null || dict.length == 0){
                return s;
            }
            
            int strLen = s.length();
            
            PriorityQueue<Interval> pq = new PriorityQueue<Interval>(new Comparator<Interval>(){
               public int compare(Interval i1, Interval i2){
                   return Integer.compare(i1.low, i2.low);
               } 
            });
            
            for(String sub : dict){
                if(sub == null || sub.isEmpty()){
                    continue;
                }
                int len = sub.length();
                int i = 0;
                while(i < strLen){
                    int idx = s.indexOf(sub, i);
                    if(idx < 0){
                        break;
                    }
                    
                    pq.offer(new Interval(idx, idx + len));
                    i = idx + 1;
                }
            }
    
            int cur = 0;
            int low = 0;
            int high = 0;
            StringBuilder sb = new StringBuilder();
    
            while(!pq.isEmpty()){
                Interval itv = pq.poll();
                low = itv.low;
                high = itv.high;
                
                while(!pq.isEmpty() && pq.peek().low <= high){
                    high = Math.max(high, pq.poll().high);
                }
                sb.append(s.substring(cur, low));
                sb.append(left);
                sb.append(s.substring(low, high));
                sb.append(right);
                
                cur = high;
            }
            sb.append(s.substring(cur));
            
            return sb.toString();
        }
    }
    

Log in to reply
 

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