我日哦竟然写了100多行但是还是通过了


  • 0
    G
    public class Solution {
        public String addBoldTag(String s, String[] dict) {
            List<List<Integer>> gen = new ArrayList<>();
            List<List<Integer>> res = new ArrayList<>();
            if(dict.length==0) return s;
            for(String dic:dict){
                int curlen = dic.length();
                if(curlen==0) continue;
                
                Stack<List<Integer>> sk = new Stack<>();
                
                for(int i=0;i<=s.length()-curlen;i++){
                    if(s.substring(i,i+curlen).equals(dic)){
                        int left = i;
                        int right = i+curlen;
                        List<Integer> ls = new ArrayList<>();
                        if(!sk.empty()){
                            List<Integer> lastls = sk.peek();
                            if(lastls.get(1)>=left){
                                lastls.set(1,right);
                            }else{
                                ls.add(left);
                                ls.add(right);
                                sk.push(ls);
                            }
                        }else{
                            ls.add(left);
                            ls.add(right);
                            sk.push(ls);
                        }
                    }
                }
                
                while(!sk.empty()){
                    gen.add(sk.pop());
                }
                
            }
            if(gen.size()==0) return s;
            
            Collections.sort(gen, new Comparator<List<Integer>>(){
                
               public int compare(List<Integer> l1, List<Integer> l2){
                   if(l1.get(0)==l2.get(0)){
                       return l1.get(1)-l2.get(1);
                   }
                   return l1.get(0)-l2.get(0);
               } 
            });
            
            Stack<List<Integer>> gensk = new Stack<>();
            
            for(List<Integer> tplist: gen){
                gensk.push(tplist);
            }
            
            while(!gensk.empty()){
                List<Integer> templ = gensk.pop();
    
                if(!gensk.empty()){
                    List<Integer> temps = gensk.peek();
                    int left1 = templ.get(0);
                    int right1 = templ.get(1);
                    if(left1<=temps.get(1)){
                        temps.set(1,Math.max(temps.get(1),right1));
                        temps.set(0,Math.min(temps.get(0),left1));
                    }else{
                        res.add(0,templ);
                    }
                }else{
                    res.add(0,templ);
                }            
            }
            
            while(!isduplicate(res)){
    
            	Stack<List<Integer>> gensk1 = new Stack<>();
    	        
    	        for(List<Integer> tplist: res){
    	            gensk1.push(tplist);
    	        }
    	        
    	        List<List<Integer>> res1 = new ArrayList<>();
    	        
    	        while(!gensk1.empty()){
    	            List<Integer> templ = gensk1.pop();
    	            
    	            if(!gensk1.empty()){
    	                List<Integer> temps = gensk1.peek();
    	                int left1 = templ.get(0);
    	                int right1 = templ.get(1);
    	                if(left1<=temps.get(1)){
    	                    temps.set(1,Math.max(temps.get(1),right1));
    	                    temps.set(0,Math.min(temps.get(0),left1));
    	                }else{
    	                    res1.add(0,templ);
    	                }
    	            }else{
    	                res1.add(0,templ);
    	            }            
    	        }        
    	        res = res1; 
            }
            
            String sd = "";
              
            int pre = 0;
            for(int i=res.size()-1;i>=0;i--){
                int left3 = res.get(i).get(0);
                int right3 = res.get(i).get(1);
                if(i==res.size()-1){
                    if(right3<s.length()){
                        String lasts = s.substring(right3,s.length());
                        sd = lasts+sd;
                    }
                }
                if(i!=res.size()-1){
                    if(pre>right3){
                        String rtps = s.substring(right3,pre);
                        sd =rtps + sd;
                    }
                }
                String tps = s.substring(left3,right3);
                sd ="<b>"+tps+"</b>" + sd;;
                pre = left3;
                if(i==0){
                    if(left3>0){
                        String firsts = s.substring(0,left3);
                        sd = firsts + sd;
                    }
                    
                }
                //System.out.println(sd);
            }
            
            return sd;
        }
    	
    	public boolean isduplicate(List<List<Integer>> m){
    		if(m.size()==1){
    			return true;
    		}
    		for(int i=1;i<m.size();i++){
    			List<Integer> left = m.get(i-1);
    			List<Integer> right = m.get(i);
    			if(left.get(1)>=right.get(0)){
    				return false;
    			}
    		}
    		return true;
    	}
    }
    

Log in to reply
 

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