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

本文主要是介绍【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;}