【Java刷题篇】串联所有单词的子串

这里写目录标题

📃1.题目
📜2.分析题目
📜3.算法原理
🧠4.思路叙述
- ✍1.进窗口
- ✍2.判断有效个数
- ✍3.维护窗口
- ✍4.出窗口
💥5.完整代码

📃1.题目

力扣链接: 串联所有单词的子串
在这里插入图片描述

📜2.分析题目

阅读题目后，可以拿到一个关键信息–words中所有字符串长度相等,这后续解题思路的一大关键，还有就是串联字串的字符串顺序可以不同。得到这两个关键信息后，我们就很容易联想到运用滑动窗口这个算法来解决问题。
好分析完题目后，我们就开始讲解算法的原理，如果你懂得滑动窗口的原理话，可以跳过直接观看算法原理的讲解。

📜3.算法原理

在此篇文章前，已经发布关于滑动窗口的讲解。
博客链接: 滑动窗口

🧠4.思路叙述

先前滑动窗口解决的问题，要么是一个数字一个数字进行遍历，要么是一个字符一个字符进行遍历，今天这题与众不同的是以一个字符串为单位进行遍历，使用哈希表来进行存储。

我们创建两个哈希表。
我们将words中的字符串存入哈希表1中。
我们在循环遍历s的过程中，每遍历一个字符串就将其加入哈希表2中
并且同时进行有效个数的判断以及维护窗口
最后通过有效个数的比较返回值

✍1.进窗口

还是定义left和right左右指针来对窗口进行划分。每一次right和left指针递增的长度是words中字符串的长度，此时有一个难题，那就是从什么位置开始遍历呢？从第一个字符的位置开始遍历？
在这里插入图片描述
那么这种情况该如何处理？这种情况行不通，我们可以每个位置都进行尝试
从0–len的位置都进行尝试，这样就完美的解决了这个问题。

 int len = words[0].length();
 for (int i = 0; i < len; i++) {
 //整体大循环控制
 }

✍2.判断有效个数

我们创建两个哈希表。

HashMap<String,Integer> hashMap1 = new HashMap<>();
HashMap<String,Integer> hashMap2 = new HashMap<>();

我们将words中的字符串存入哈希表1中。

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

首先确定循环的条件，由上述讲解中已经提到right的起始位置

 for (int right = i,left = i,count = 0; right+len <= s.length() ; right+= len) {
 
 }

我们在循环遍历s的过程中，每遍历一个字符串就将其加入哈希表2中，并且与哈希表1中存入的字符串进行比较，如果相同，有效个数就+1

   String in = s.substring(right,right+len);
       hashMap2.put(in,hashMap2.getOrDefault(in,0)+1);
   if (hashMap2.get(in) <= hashMap1.getOrDefault(in,0)){
   count++;
  }

✍3.维护窗口

再次过程中，我们要保证窗口的大小。同words中字符个数相等的窗口。

     int len = words[0].length();
     int m = words.length;
     if (right - left +1 > m*len){
        //出窗口
     }

✍4.出窗口

  String out = s.substring(left,left+len);
  if (hashMap2.get(out) <= hashMap1.getOrDefault(out,0)){
        count--;
     }
      hashMap2.put(out,hashMap2.get(out)-1);
     left+= len;

💥5.完整代码

 public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int len = words[0].length();
        int m = words.length;
        HashMap<String,Integer> hashMap1 = new HashMap<>();
        for (String ss:words) {
            hashMap1.put(ss, hashMap1.getOrDefault(ss,0)+1);
        }
        //大条件
        for (int i = 0; i < len; i++) {
            HashMap<String,Integer> hashMap2 = new HashMap<>();
            //入口位置的处理
            for (int right = i,left = i,count = 0; right+len <= s.length() ; right+= len) {
            //进窗口
                String in = s.substring(right,right+len);
                hashMap2.put(in,hashMap2.getOrDefault(in,0)+1);
                //有效个数的判断
                if (hashMap2.get(in) <= hashMap1.getOrDefault(in,0)){
                    count++;
                }
                //窗口大小的维护
                if (right - left +1 > m*len){
                //出窗口
                    String out = s.substring(left,left+len);
                    if (hashMap2.get(out) <= hashMap1.getOrDefault(out,0)){
                        count--;
                    }
                    hashMap2.put(out,hashMap2.get(out)-1);
                    left+= len;
                }
                //判断条件是否符合要求
                if (count == m){
                    list.add(left);
                }
            }
        }
        return list;
    }