Java solution, Same as Merge Interval.


  • 8
    X

    Consider you have string
    s = "aaabbcc"
    dict = ["aaa","aab","bc"]

       you find the index of each string in dict, conver to an interval, you will get
       
       [[0, 3], [1, 4], [4, 6]]
         aaa     aab      bc
       then combine these intervals
       
       Ater merged, we got [0,6], so we know "aaabbc" needs to be surrounded by tag. 
    
    public String addBoldTag(String s, String[] dict) {
            List<Interval> intervals = new ArrayList<>();
            for (String str : dict) {
            	int index = -1;
            	index = s.indexOf(str, index);
            	while (index != -1) {
            		intervals.add(new Interval(index, index + str.length()));
            		index +=1;
            		index = s.indexOf(str, index);
            	}
            }
            System.out.println(Arrays.toString(intervals.toArray()));
            intervals = merge(intervals);
            System.out.println(Arrays.toString(intervals.toArray()));
            int prev = 0;
            StringBuilder sb = new StringBuilder();
            for (Interval interval : intervals) {
            	sb.append(s.substring(prev, interval.start));
            	sb.append("<b>");
            	sb.append(s.substring(interval.start, interval.end));
            	sb.append("</b>");
            	prev = interval.end;
            }
            if (prev < s.length()) {
            	sb.append(s.substring(prev));
            }
            return sb.toString();
        }
    	
    	class Interval {
    		int start, end;
    		public Interval(int s, int e) {
    			start = s;
    			end = e;
    		}
    		
    		public String toString() {
    			return "[" + start + ", " + end + "]" ;
    		}
    	}
    	
    	public List<Interval> merge(List<Interval> intervals) {
            if (intervals == null || intervals.size() <= 1) {
                return intervals;
            }
            Collections.sort(intervals, new Comparator<Interval>(){
                public int compare(Interval a, Interval b) {
                    return a.start - b.start;
                }
            });
            
            int start = intervals.get(0).start;
            int end = intervals.get(0).end;
            List<Interval> res = new ArrayList<>();
            for (Interval i : intervals) {
                if (i.start <= end) {
                    end = Math.max(end, i.end);
                } else {
                    res.add(new Interval(start, end));
                    start = i.start;
                    end = i.end;
                }
            }
            res.add(new Interval(start, end));
            return res;
        }
    

  • 0
    T

    Nice solution! Slightly simplify your method!

    public class Solution {
        public class interval{
            int start;
            int end;
            interval(int start,int end){
                this.start=start;
                this.end=end;
            }
        }
        public String addBoldTag(String s, String[] dict) {
            List<interval> list = new ArrayList<>();
            for(String str:dict){
                int index=s.indexOf(str,0);
                while(index!=-1){
                     list.add(new interval(index,index+str.length()));
                     index=s.indexOf(str,index+1);
                }
            }
            Collections.sort(list,new Comparator<interval>(){
                public int compare(interval a,interval b){
                    return a.start-b.start;
                }
            });
            List<interval> res = mergeInterval(list);
            
            int pre=0;
            StringBuilder sb = new StringBuilder();
            for(interval ele:res){
                 sb.append(s.substring(pre,ele.start));
                 sb.append("<b>"+s.substring(ele.start,ele.end)+"</b>");
                 pre=ele.end;
            }
            
            if(pre<s.length()){
                sb.append(s.substring(pre));
            }
            
            return sb.toString();
        }
        
        public List<interval> mergeInterval(List<interval> list){
            List<interval> res = new ArrayList<>();
            if(list==null || list.size()==0){
                 return res;  
            } 
            
            res.add(list.get(0));
            for(int i=1;i<list.size();i++){
                 interval temp=list.get(i);
                 if(temp.start>res.get(res.size()-1).end){
                     res.add(temp);
                 }else{
                     int max=Math.max(res.get(res.size()-1).end,temp.end);
                     res.get(res.size()-1).end=max;
                 }
            }
            return res;
        }
    }
    

Log in to reply
 

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