2022-03-08 2055. 蜡烛之间的盘子+ II 063

双指针第一遍超时，优化了一下勉强通过，没看到题目下面的数据量大小。
应该还能再优化一波，不过感觉会很麻烦，懒。。。
java版本：

class Solution {
    public int[] platesBetweenCandles(String s, int[][] queries) {

        // 找最左和最右边的两个蜡烛 ||
        // 然后找里面有几个盘子  *
        // left right
        // 双指针
        int left,right,count;
        int n=queries.length;
        int[] res=new int[n];
        int arr_count=0;
           
            for(int i=0;i<s.length();i++){
                if(s.charAt(i)=='|'){
                       arr_count++;
                }  
            }
            if(arr_count==0){
                return res;
            }
            
             int[] arr=new int[arr_count];
             int index=0;
           for(int i=0;i<s.length();i++){
                if(s.charAt(i)=='|'){
                arr[index]=i;
                index++;
                }  
            }
            int left_index,right_index;


        for(int i=0;i<n;i++){
            count=0;
           left_index=0;
           right_index=arr_count-1;
           left=queries[i][0];
           right=queries[i][1];
         
                while( left_index<right_index && left>arr[left_index]  ){
                    left_index++;
               }
                while(left_index<right_index && right<arr[right_index]){
                 right_index--;
               }
            //    System.out.println(arr[left_index]);
            //        System.out.println(arr[right_index]);
           
          
           count=arr[right_index]-arr[left_index]-(right_index-left_index-1)-1;
           
           res[i]=count;
        }
        return res;

    }
}

前缀树中规中矩，记不清leetcode咋导入需要的包了，import导入Stringutils报错。。。
java版本：

class Solution {

 class Trbie{
    private Trbie[] children;
        private boolean isEnd;
    public Trbie() {
        children=new Trbie[26];
        isEnd=false;
     
    }
 }

    /** Inserts a word into the trie. */
    public  void insert(Trbie root,String word) {
        Trbie node=root;
       
        for(int i=0;i<word.length();i++){
            int index=word.charAt(i)-'a';
            if(node.children[index]==null){
            node.children[index]=new Trbie();
            }
            node=node.children[index];
        }
        node.isEnd=true;
    return ;

    }
         public  int search(Trbie root,String s){
             Trbie node=root;
             int count=0;
              for(int i=0;i<s.length();i++){
             int index=s.charAt(i)-'a';
           if(node.children[index]==null || node.isEnd){
               break;
           }else{
              count++;
           }
           node=node.children[index];
        
         
        }
        // System.out.println(count);
        if(node.isEnd && count!=0){
         return count;
        }else{
            return 0;
        }
       


         }
    
    public String replaceWords(List<String> dictionary, String sentence) {

        // 确定每一个单词是否有其前缀
        Trbie node=new Trbie();
          for(int i=0;i<dictionary.size();i++){
            insert(node,dictionary.get(i));
          }

      String[] str=sentence.split(" ");
      int n=str.length;
      int[] arr=new int[n];
      for(int i=0;i<n;i++){
          int temp=search(node,str[i]);
          if(temp!=0){

              
            str[i]=str[i].substring(0,temp);
          }
      }
      StringBuffer str_buffer = new StringBuffer();
for (int i=0;i<n;i++) {
    str_buffer.append(str[i]);
   if(i!=n-1){
  str_buffer.append(" ");
   }
   
}
    String res=str_buffer.toString();
    return res;
    }
}