Substring with Concatenation of All Words(字符串数组全排列在给给丁字符串的索引位置)leetcode30

￡神魔★判官ぃ 2022-05-23 10:12 83阅读 0赞

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

Input:
      s = "barfoothefoobarman",
      words = ["foo","bar"]
    Output: [0,9]
    Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
    The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
      s = "wordgoodstudentgoodword",
      words = ["word","student"]
    Output: []

code（超时 ）

List<String> sort=new ArrayList<>();
        int length=0;
        public List<Integer> findSubstring(String s, String[] words) {
             List<Integer> indexs=new ArrayList();
            if(s.isEmpty()||words.length<1)
                return indexs;
            
            for(int i=0;i<words.length;i++){
                length+=words[i].length();
            }
           
            allSort(words,new StringBuilder(),new boolean[words.length]);
            findIndex(s,sort,indexs);//此处也可以用28题的方法查找
            Collections.sort(indexs);
            for(int j=1;j<indexs.size();){
                if(indexs.get(j)==indexs.get(j-1)){  
                    indexs.remove(j);
                }else{
                    j++;
                }
            }
            return indexs;
        }
        void findIndex(String s,List<String> sort,List<Integer> indexs){
            for(int i=0;i<sort.size();i++){
                int index=s.indexOf(sort.get(i));
                while(index!=-1){
                    indexs.add(index);
                    index=s.indexOf(sort.get(i),index+1);
                }
            }
        }
        void allSort(String[] words,StringBuilder builder,boolean[] isVisit){
            if(builder.length()==length){
                sort.add(builder.toString());
                return;
            }   
            for(int i=0;i<words.length;i++){
                if(isVisit[i])
                    continue;
                if(i!=0&&words[i].equals(words[i-1])&&!isVisit[i-1])
                    continue;
                isVisit[i]=true;
                allSort(words,builder.append(words[i]),isVisit);
                isVisit[i]=false;
                builder.delete(builder.length()-words[i].length(),builder.length());
            }
        }