leetcode 30. 串联所有单词的子串（优质解法）

代码：

class Solution {
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> integerList=new ArrayList<>();

        int length=words.length;    //words 数组中的字符串个数
        int size=words[0].length(); //words 数组中每个字符串的长度

        HashMap<String,Integer> hashMap1=new HashMap<>();   //存储 words 数组中字符串以及出现的个数


        //把 words 数组中字符串以及出现的个数保存到 hashMap1 中
        for(String str:words){
            hashMap1.put(str,hashMap1.getOrDefault(str,0)+1);
        }

        for(int i=0;i<size;i++){
            int count=0;    //记录当前子串中符合条件的字符串
            HashMap<String,Integer> hashMap2=new HashMap<>();   //存储讨论的子串中字符串以及出现的个数
            for(int left=i,right=i;right+size<=s.length();right+=size){
                //把 right 指针指向的数据入窗口
                String in=s.substring(right,right+size);
                hashMap2.put(in,hashMap2.getOrDefault(in,0)+1);

                //判断当前入窗口的字符串是否是符合条件的
                if(hashMap2.get(in)<=hashMap1.getOrDefault(in,0)){
                    count++;
                }

                //判断当前子串的长度是否过长，是否需要出窗口
                if(right-left+1>length*size){
                    String out=s.substring(left,left+size);
                    //判断出窗口的字符串是否是有效字符串
                    if(hashMap2.get(out)<=hashMap1.getOrDefault(out,0)){
                        count--;
                    }
                    hashMap2.put(out,hashMap2.get(out)-1);
                    left+=size;
                }

                //判断有效字符串个数是否符合条件
                if(count==length){
                    integerList.add(left);
                }
            }
        }
        return integerList;
    }
}

题解：

? ? ? ? 本题的含义表达得很明确，我们需要在字符串 s 中找到一个子串，子串由字符串数组 words 中的字符串以不同顺序组成

? ? ? ? 我们首先可以想到一个暴力解法，遍历出字符串 s 中的所有子串，找出完全由 words 中的字符串以不同顺序组成的子串。现在就涉及到一个问题，我们如何知道子串是完全由 words 中的字符串以不同顺序组成的

? ? ? ? 我们可以利用哈希表 hash1 和 hash2 存储 words 数组中和子串中字符串的相关信息，以字符串为 key ，个数为 value ，然后比对 hash1 和 hash2 中的内容，便知道当前子串是否是符合条件的

? ? ? ? 假设输入：s = "barfoothefoobar", words = ["foo","bar"]

? ? ? ? 首先我们可以获得的信息是，words 数组中的字符串个数 length = 2，每个字符串的大小 size = 3 ，由于我们要遍历所有的子串，所以让 L 和 R 指针指向下标为 0 的位置。我们将 words 数组中的相关信息保存到哈希表 hash1 中，foo-1，bar-1，用变量 count 记录子串中有效字符串的个数

????????? 因为符合要求的子串是由 words 数组中的字符串按不同顺序组成的，而 words 数组中的字符串是 3 个字符为一个整体，所以我们在寻找子串的时候也以 3 个字符为一个整体，R 指针指向当前位置，通过?s.substring(right,right+size) 取出字符串 bar，将 bar - 1 保存到 hash2 中，由于在hash1 中 bar-1，只要子串中的字符个数小于等于 wors 数组中对应字符的个数，就代表该字符是有效字符，所以 bar 是有效字符，此时 count++，count=1

b????????a????????r????????f????????o????????o????????t????????h????????e????????f????????o????????o????????b????????a????????r? ? ??

L

R

? ? ?录入字符串 bar 的信息以后，R 指针向右移动 size 位，录入下一个字符串 foo，将 foo- 1 保存到 hash2 中，由于在hash1 中 foo-1，，所以 foo 是有效字符，此时 count++，count=2，因为此时子串为 barfoo 长度为 6 == size*length ，并且 count == 2 == length，所以该子串是符合要求的，我们就直接记录 L 指针指向的下标 0

b????????a????????r????????f????????o????????o????????t????????h????????e????????f????????o????????o????????b????????a????????r? ? ??

L

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?R??

? ? ? ? 当 R 指针再向右移 size 位以后，子串为 barfoothe，大小为 9 > size * length ，字符数都比 words 数组中的字符数多了，肯定不符合要求，代表以 L 指针为首的子串已经讨论完毕，让 L 指针向右移动 size 位，讨论下一组字符串

b????????a????????r????????f????????o????????o????????t????????h????????e????????f????????o????????o????????b????????a????????r? ? ??? ? ?

L

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?R? ? ?? ?

? ? ? ? L 指针之前指向的是字符串 bar ，bar 在 hash2 中的个数为 1，小于等于在 hash1 中的个数，所以是有效字符串，因此在将 L 指针移动前，我们需要修改?hash2 中的 bar - 0，count = 1，

此时子串的长度符合要求，但是有效字符串个数 count < length，所以该子串不符合要求，让 R 指针向右移动 size 位?

b????????a????????r????????f????????o????????o????????t????????h????????e????????f????????o????????o????????b????????a????????r? ? ??? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? L??

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?R?

? ? ? ? 之后循环上述操作即可

? ? ? ? 有细心的小伙伴会发现，上面的流程没有讨论完所有的子串，我们还需要以如下的两种情况，继续上述的操作,也就是在上述的循环操作要执行 size 次

b????????a????????r????????f????????o????????o????????t????????h????????e????????f????????o????????o????????b????????a????????r? ? ??? ? ?

???????????L

? ? ? ? ? ?R

? ??

b????????a????????r????????f????????o????????o????????t????????h????????e????????f????????o????????o????????b????????a????????r? ? ??? ? ?

????????????????????L

? ? ? ? ? ??????????R

? ????