算法刷题:最小覆盖子串

最小覆盖子串

• .
• 题目链接
• 题目详情
• 题目解析
• 算法原理
• • 滑动窗口流程图
  • 定义变量
  • 进窗口
  • 判断
  • 出窗口
  • 更新结果
  • index.php/tags-41973.html" >���的答案

    .

    题目链接

    最小覆盖子串

    题目详情

    题目解析

    这道题的要求是在s字符串中找到包含t字符串中所有字母的子串,并要求找到长度最小的,很显然,这道题适合用滑动窗口来解决

    算法原理

    滑动窗口流程图

    定义变量

    双指针的初始值都为0

    定义hash表记录t和窗口中的字母个数

    定义变量统计t和窗口内的有效字母种类

    有效字母种类:

    窗口内hash某个字母的个数大于等于t的hash中的该字母的个数时,为有效

    定义变量,记录最小子串的初始值和长度

    进窗口

    将right所在字母存到hash中,并维护窗口内有效字母种类:

    当窗口内hash某个字母的个数等于t的hash中的该字母的个数时,变量加一

    判断

    t和窗口内的有效字母种类相同时,进行更新结果,然后出窗口,找到下一个满足条件的子串

    出窗口

    出窗口之前,需要维护窗口内有效字母种类,如果当前要出窗口的字母的个数正好等于t的hash中的该字母的个数,出窗口之后,窗口内有效种类会减少,因此需要提前维护

    更新结果

    比较当前窗口的长度与之前的最小长度,更新最小子串的初始值和长度

    我的答案

    class Solution {    public String minWindow(String s, String t) {        //定义变量,记录子串初始值        int begin = -1;        //定义变量记录最小长度        int len =Integer.MAX_VALUE;        // 将两个字符串转成数组,方便遍历        char[]ss = s.toCharArray();        char[]tt = t.toCharArray();        //创建hash1,记录t        int[]hash1 = new int[128];        //定义变量记录tt中字母的种类        int core = 0;        for(int tmp:tt){            if(hash1[tmp]==0) core++;            hash1[tmp]++;        }        //创建hash2,记录窗口        int[]hash2 = new int[128];        //定义变量记录窗口内有效种类        int count = 0;        //定义指针        for(int left = 0,right = 0;right            //进窗口            char in = ss[right];            hash2[in]++;            //维护有效种类            if(hash2[in]==hash1[in]) count++;            //判断            while(count==core){                //满足条件,更新结果(子串的最小长度)                if(lenright-left+1){                    begin=left;                    len =right-left+1;                 }                char out = ss[left];                //维护有效种类                if(hash2[out]==hash1[out]) count--;                //出窗口                hash2[out]--;                left++;            }        }        if(begin==-1) return new String();        return s.substring(begin,begin+len);    }}