每天题解:LeetCode 76. 最小覆盖子串

Author Avatar
清水雅然君 05月 23,2020

最小覆盖子串

题目链接

题目描述

给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。

示例:

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明:

如果 S 中不存这样的子串,则返回空字符串 ""。
如果 S 中存在这样的子串,我们保证它是唯一的答案。

解法

class Solution {
    public String minWindow(String s, String t) {
   //空值判断
        int sLen = s.length();
        int tLen = t.length();
        if (sLen == 0 || tLen == 0 || sLen < tLen) {
            return "";
        }
        char[] tArr = t.toCharArray();
        char[] sArr = s.toCharArray();
        //初始化一个128数组
        int[] tLetter= new int[128];
        for (char c : tArr) {
            tLetter[c]++;
        }
        //出现的字符的个数
        int reduce = tLen;
        //区间长度
        int len = sLen+1;
        int start = 0;
        int left = 0;
        int right = 0;
        while (right < sLen) {
            if (tLetter[sArr[right]] > 0) {
                reduce--;
            }
            tLetter[sArr[right]]--;
            right++;
            //个数达到
            while (reduce == 0) {
                if ((right - left) < len) {
                    len = right - left;
                    start = left;
                }
                //左边的指针开始压缩
                tLetter[sArr[left]]++;
                if (tLetter[sArr[left]] > 0) {
                    reduce++;
                }
                left++;
            }
        }
       if (len == sLen+1) {
            return "";
        }
        return s.substring(start, start + len);
    }
}

分析思路

首先承认由于这题属于困难等级,我的功力不够,也是参考别人的写法进行了逐步分解,理解,再写出。
1.根据题目的实例分析

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC

要求在S字符串找到最小包含T的字符的最小子串。
S字符串中可以找到 "ADOBEC",“EBANC”,"BANC",其中符合条件的只有结果 "BANC"
假设我们有left和right,两个指针标表示字串的下标分别为[0,5],[8,12],[9,12],==> s[left, right] 其中覆盖字符T。
1定义 left, right 分别覆盖区间的左右边界

int left = 0; int right = 0;

2.然后right指针开始右移动,直到覆盖了字符T,这里问题便出现了,如何知道s[left, right]中已经覆盖了T?
覆盖条件为含有全部的T字符,已知T的个数,我们假设一个变量int reduce = tLen;当找到一个符合条件的字符,我们便减去一个,直到变量reduc为0,表示s[left, right]中已经覆盖了T
3。查找到一个已经覆盖T的子串,我们怎么知道当前的s[left, right]是否是最小的长度的字串?
我们初始化一个变量用于表示最短的字符的长度 int len = sLen(S字符的长度)+1;这里将初始值设置为问slen(S字符的长度)+1,避免类似出现S="A",T="B", 如果 S 中不存这样的T子串,我们方便做一个判断
3.1 初始化 `int len = sLen+1;
3.2 对符合的字串,我们进行长度len的赋值

if ((right - left) < len) {
 len = right - left;
 }

4.知道字串的长度后,我们最终是要最S字符进行切割,这里就必须有两个变量beginIndex,endIndex

 String substring(int beginIndex, int endIndex)

4.1 初始化一个变量 int start = 0; 便是我们要切割的字符起点
4.2 对符合字串的,我们进行起点start 的的赋值

if ((right - left) < len) {
len = right - left;
start = left;
 }

5.我们已经知道第一个字串的s[left, right],right指针再右移动,已经没有意义,因为再往右边扩展再得到一个T字符,不满足题目的最小字串。既然 right不能移动,那我们试试动动left?
5.1现在要移动 left 指针,假如我们遇到在s[left]符合T字符的,这个时候我们应该做什么?
假设AXX,我们当前指针[left]=A,我们抛弃掉A,继续往XX滑动,之前我们设置了一个全局变量reduce表示,s[left, right]中符合T字符的个数,抛弃掉一个T字符,我们需要将reduce++;标识我们s[left++, right]中,reduce++只是增加,我right需要寻找T字符的个数,但是并不能知道需要寻找的字符是什么?
如:AXXBC,去掉A后,reduce++,right指针需要需要一个新的字符,维持字串reduce平衡,剩下的字符为XXBCB,right右移动,虽然维持了reduce,但是不符合我们的要求包含全部的T
一,维护一个map用于记录s[left, right]字串中的每个T字符的个数变化
二,维护一个长度为128(大小写字母)的int数组
这里我们使用了第二种方式

 int[] tLetter= new int[128];
.......
 tLetter[sArr[left]]++; 个数加1
 if (tLetter[sArr[left]] > 0) {
 reduce++;  
 }
 left++;

6.这里我们基本上的代码基本上完成,还需要做一些
6.1 初始化数组,记录一开始每个T字符的个数

   int[] tLetter= new int[128];
   for (char c : tArr) {
            tLetter[c]++;
  }

6.2 遇到T字符减少格式

 if (tLetter[sArr[right]] > 0) {
 reduce--;
}
 tLetter[sArr[right]]--;

于是整个代码进行dubug测试,完成提交