串联所有单词的子串

别问为啥距离昨天的两数相除，我这么快就又搬了一题上来，问就是我太菜（是真的菜，，咋都这么难）

今天，，其实昨天做的这道题—串联所有单词的子串，一直做到今天上午，最终还是输在了效率上，为啥子我的代码总是运行的这么慢？？或许这就是大佬与我这种菜鸡的区别所在

题目介绍

给定一个字符串s和一些长度相等的单词words。找出s中恰好可以由words中所有单词串联形成的子串的起始位置。

注意，子串要与words中的单词完全匹配，中间不能有其他字符，不考虑串联顺序

举例：

    输入：s = "barfoothefoobarman", words = ["foo","bar"]
    输出：[0,9]
    解释：
    从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
    输出的顺序不重要, [9,0] 也是有效答案。

我的思路1

首先说下，我的思路在leetcode中也通过了，只是在效率上，实在是看不过去，刷新了我刷题上运行效率的下限（运行时间在2000左右，内存在38左右）

我的思路比较简单，i指向s的开头，j指向words的第一个元素，利用一个和words同样大小的bool数组表示元素是否已被使用。然后，就是从当前的i向后判断words大小个单词，如果全部符合，就记录下i，否则，就直接break，将i加1。代码如下：

public List<Integer> findSubstring(String s, String[] words){
    int len = words[0].length();
    int i = 0;
    String g = "";
    for(int m=0;m<words.length;m++){
        g += words[m];
    }
    if(g.equals(s)){
        return new ArrayList<>(Arrays.asList(0));
    }

    Boolean[] tag = new Boolean[words.length];
    Arrays.fill(tag,Boolean.FALSE);
    List<Integer> ans = new ArrayList<>();
    while(i<s.length()){
        int j = 0;
        int i_temp = i;      //（1）
        while(j<words.length && i+len<=s.length()){
            if(s.substring(i,i+len).equals(words[j]) && tag[j]!=true){
                tag[j] = true;
                j = 0;
                i = i + len;
                continue;
            }
            j++;
        }
        if(!Arrays.asList(tag).contains(false)){
            ans.add(i_temp);
        }
        Arrays.fill(tag,Boolean.FALSE);
      	i = i_temp + 1;
    }
    return ans;
}

其实导致这个算法很慢的原因在于，我对i的移动范围太大，而且我没有一次性移动words的总长度，只是一个单词的长度

优化：可以在（1）后面直接将i到i+len_sum的子串提出来，再利用while循环判断该子串里是否包含了words里的所有单词，是则记录下当前的i，不是就恢复标志数组tag，并跳出while循环，直接将i加1

我的思路2

按照刚才思路一后的优化，加上代替tag数组的HashMap，得出了下面的思路：

public List<Integer> findSubstring(String s, String[] words){
    if(s==null || words==null || s.equals("")){
        return new ArrayList<>(Arrays.asList(0));
    }

    int word_num = words.length;
    int one_word = words[0].length();
    int len_sum = word_num * one_word;   //窗口大小
    List<Integer> ans = new ArrayList<>();

    HashMap<String,Integer> map = new HashMap<>();

    for(String word : words){
        map.put(word,map.getOrDefault(word,0)+1);
    }

    for(int i=0;i<=s.length()-len_sum;i++){
        String word_temp = s.substring(i,i+len_sum);
        HashMap<String,Integer> map_temp = new HashMap<>(map);
        //判断该窗口中的单词是否刚好为给的单词
        int j = 0;
        boolean flag = true;
        while(j+one_word<=len_sum){
            String word = word_temp.substring(j,j+one_word);
            if(map_temp.containsKey(word) && map_temp.get(word)>0){
                map_temp.put(word,map_temp.get(word)-1);
                j = j + one_word;
            }else{
                flag = false;
                break;
            }
        }
        if(flag==true){
            ans.add(i);
        }
    }
    return ans;
}

这个思路里，精彩的地方就是利用HashMap记录words里每个单词的个数，便于判断我们截取下来的子串里的单词是否为words里的，以及是否被使用过的（用过一次就将个数减1，直到0）

大佬的思路

关于这种对字符串与其子串的类似的题目，可以想想滑动窗口的方法是否可以用

大致上的思路其实是类似的，只是这个思路的外循环只需要经历单个words里的单词长度，因为这样s里所有的单词都会被访问到

先看代码吧，边看代码边解释：

public List<Integer> findSubstring(String s, String[] words){
    if(s==null || words==null || s.equals("")){
        return new ArrayList<>(Arrays.asList(0));
    }
    int one_word = words[0].length();
    int word_num = words.length;
    int len = s.length();
    List<Integer> ans = new ArrayList<>();

    HashMap<String,Integer> map = new HashMap<>();
    for(String word:words){
        map.put(word,map.getOrDefault(word,0)+1);
    }
    for(int i=0;i<one_word;i++){
        int left = i;
        int right = i;
        int count = 0;
        HashMap<String,Integer> map_temp = new HashMap<>();
        while(right+one_word<=len){
            String word = s.substring(right,right+one_word);
            right += one_word;
            map_temp.put(word,map_temp.getOrDefault(word,0)+1);
            count++;
            //关键
            while(map_temp.getOrDefault(word,0)>map.getOrDefault(word,0)){
                String word_temp = s.substring(left,left+one_word);
                map_temp.put(word_temp,map_temp.get(word_temp)-1);
                left += one_word;
                count--;
            }
            if(count==word_num){
                ans.add(left);
            }
        }
    }
    return ans;
}

首先，依旧是利用HashMap（map1）将单词的个数记录下来；接着，在循环的内部，首先定义left与right，left是指当前窗口的左边，right自然就是右边，新建一个map2，存放截取的子串里的单词个数（可能会有map1里没有的，没关系，继续看），count是用来记录当前子串里已经加入map2的个数

对当前截取子串的操作：将子串里的单词放进map2，并记录其次数，同时right移动，count++，再将该单词在map2里的次数与map1里比较，如果大于，则表明当前单词在该窗口中要么已经用完了，要么直接map1里没有该单词，于是当前的left-right窗口不行，便移动left，将窗口整体向后移，至于移到什么地方呢？

String s = "wordgoodgoodgoodbestword";
String[] d = new String[]{"word","good","best","good"};

以这个例子举例说明：当left在0，right移到第三个good的时候，会发现good用完了，那么就需要移动left，自然而然想到，需要将当前窗口移到第三个good刚好将good用完的地方，也就是将left移到第二个good的开头处。

实际上，如果当前的子串单词是map1里没有的，那么就可以直接将left移到right（该没有单词的下一个单词的开头）处，比如说：

String s = "wordgoodgaodgoodbestword";
String[] d = new String[]{"word","good","best","good"};

当前left在0，right在8，获取”goad”子串后，right=12，发现”goad”在map1里没有，那么直接可以将left移到12

一定要记住：我们的每一轮开始都是有个基准的，比如说，上面这个例子的基准就是当前的i=0，意思就是说，必须从0开始往后每四个是一个单词

结束

以上就是我这个菜鸡在这道题上的一点理解，还是得膜拜各种大佬@—@

（希望明天的题目不至于再让我来写一篇博客记录了）