📃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中字符个数相等的窗口。文章来源:https://www.toymoban.com/news/detail-842302.html
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;
}
以上就是所有内容,如果对你有帮助的话,点赞收藏支持一下吧!💞💞💞文章来源地址https://www.toymoban.com/news/detail-842302.html
到了这里,关于【Java刷题篇】串联所有单词的子串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!