Leetcode初学——串联所有单词的子串

题目：

我认为这道题要做出来是不难的，主要是怎么使他的效率变高

可惜我仅仅只是将这道题做出来，深感惭愧

我的思路可以算是滑动窗体吧

因为words中的每个单词的长度相同，所以我们已知这个长度

以这个长度作为我们窗体的长度，在s中寻找是否有在words中存在的单词

有的话，删除words中存在的这个单词，继续往后找，如果中间断开，则words恢复原样

 

这里，为了方便对words进行操作，我将words转换为list

请看代码：

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res=new ArrayList<Integer>();
        List<String> str=new ArrayList<String>(Arrays.asList(words));
        //如果s和words有一样为空的话，那么直接返回空列表
        if(s.length()==0 || words.length==0) return res;
        int n=words[0].length();
        for(int i=0;i<=s.length()-n;i++){
            //每次循环重新配置temp
            List<String> temp=new ArrayList<String>();
            temp.addAll(str);
            if(temp.contains(s.substring(i,i+n))){
                int j=i+n;
                //当s后面的字符串长度小于words中所有单词的总长度时，直接退出循环
                if(s.length()-i<temp.size()*n) break;
                //删除temp中第一个符合条件的单词
                //如果用remove的话，会把temp中所有符合条件的单词都删去，会报错！
                temp.remove(temp.indexOf(s.substring(i,i+n)));
                while(temp.isEmpty()==false){
                    if(temp.contains(s.substring(j,j+n))){
                        temp.remove(temp.indexOf(s.substring(j,j+n)));
                        j+=n;
                    }else{
                        break;
                    }
                }
                //如果temp为空，说明是都满足条件的，可以把i加入结果集
                if(temp.isEmpty()) res.add(i);
            }
        }
        return  res;
    }
}

运行结果如下：