LeetCode30.串联所有单词的子串

题目链接：30. 串联所有单词的子串 - 力扣（LeetCode）

1.暴力解法（会超时）

由于题目中要判断s中是否有子串符合words，于是可以定义一个hashMap来存储words中的字符串的信息；

定义变量len表示words中字符串的数目，strLen表示每个字符串的长度（words中的字符串长度相同）；

遍历s，每次取出长为len * strLen长度的子字符串，再遍历这个子字符串，每次取出子字符串中长为strLen的字符串放到另一个hashMap1中，子字符串遍历完成后，hashMap1中就存储了子字符串中的子串信息，再将这两个map进行比较，判断是否相等，若相等，及说明这两个子串是相同的（顺序不同是可以的），将下标存储到结果集中，继续遍历s，代码如下：

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        int len = words.length;//words中字符串个数
        int strLen = words[0].length();//words中每个字符串的长度
        Map<String, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < len; i++) {
            hashMap.put(words[i], hashMap.getOrDefault(words[i], 0) + 1);
        }
        int sLen = s.length();
        for (int i = 0; i < sLen - len * strLen + 1; i++) {
            boolean flag = true;
            Map<String, Integer> hashMap1 = new HashMap<>();
            for (int j = i; j < len * strLen + i; j += strLen) {
                String subString = s.substring(j, j + strLen);
                hashMap1.put(subString, hashMap1.getOrDefault(subString, 0) + 1);
            }
            if (hashMap.equals(hashMap1)) {
                ret.add(i);
            }
        }
        return ret;
    }

2.滑动窗口

在438. 找到字符串中所有字母异位词 - 力扣（LeetCode）中，使用了滑动窗口，由于本题与这一题的思想差不多，于是也可以使用滑动窗口；

和暴力解法一样，需要定义一个hashMap来存储words中的字符串的信息，size表示words中字符串的个数，strLen表示每个字符串的长度；

定义两个指针left和right，两指针均指向0下标位置，再定义一个count表示hashMap1中有效字符串的个数；

每次让right向后移动strLen个单位，将right与right+ strLen之间的子串subString放入hashMap1中，比较hashMap中subString的值与hashMap1中的值，若后者大，表示subString不是有效子串，反之，count++；

让right与left之间的距离大于等于size * strLen时，就移动left，取出left与left + strLen之间的子串subString1，若hashMap1中subString1的值小于等于hashMap中的值，就表示subString1是一个有效的子串，将count--，left向右移动strLen，反之直接将left向右移动strLen，当count与size相等时，就说明这个子串符合条件，将left存入结果集中；

注意：

由于会有以下三种遍历方式，于是right一开始可能并不会从0下标开始，但每size次循环后的遍历过程是一样的，就可以再for循环外再套上一层循环，这个循环执行size次，原理图如下：

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        int size = words.length;//words中字符串个数
        int strLen = words[0].length();//每个字符串的长度
        Map<String, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < size; i++) {//将words中的字符串信息存入hashMap中
            hashMap.put(words[i], hashMap.getOrDefault(words[i], 0) + 1);
        }
        int sLen = s.length();
        int n = 0;
        while (n < strLen) {//循环size次
            Map<String, Integer> hashMap1 = new HashMap<>();
            for (int left = n, right = n, count = 0; right < sLen - strLen + 1; right += strLen) {//count为有效字符串个数
                String subString = s.substring(right, right + strLen);
                hashMap1.put(subString, hashMap1.getOrDefault(subString, 0) + 1);
                if (hashMap1.get(subString) <= hashMap.getOrDefault(subString, 0)) {
                    count++;
                }
                if (right - left >= size * strLen) {
                    String subString1 = s.substring(left, left + strLen);
                    if (hashMap1.get(subString1) <= hashMap.getOrDefault(subString1, 0)) {
                        count--;
                    }
                    hashMap1.put(subString1, hashMap1.get(subString1) - 1);
                    left += strLen;
                }
                if (count == size) {
                    ret.add(left);
                }
            }
            n++;
        }
        return ret;
    }

 希望大家积极交流！！