站点图标 AI技术聚合

【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;
    }

以上就是所有内容,如果对你有帮助的话,点赞收藏支持一下吧!💞💞💞

版权声明:本文为博主作者:爱吃南瓜的北瓜原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/2202_75795446/article/details/136789297

退出移动版