• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

76. 最小覆盖子串

开发技术 开发技术 2周前 (04-29) 9次浏览

难度 hard
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。

注意:如果 s 中存在这样的子串,我们保证它是唯一的答案。

示例 1:

输入:s = “ADOBECODEBANC”, t = “ABC”
输出:”BANC”
示例 2:

输入:s = “a”, t = “a”
输出:”a”

提示:

1 <= s.length, t.length <= 105
s 和 t 由英文字母组成

进阶:你能设计一个在 o(n) 时间内解决此问题的算法吗?

解题思路:这道题目我想了很久,后来还是参考了别人的题解才解出来的,有几个关键的地方需要注意,那就是这种从子串中找最值的问题,一般都是用滑动窗口来解决的,这道题目也不例外,除了这一点之外,我想到的还有,t中出现的字母肯定要用一个数据结构保存起来,然后这个数据结构在遍历s的过程中会更新其数目,保证既能满足个数的要求,又能在滑动窗口的方法下取得最小值,因此题解如下:由于我们使用的字符串仅包含字母,因此可以用一个128维的数组来记录字母出现的关系,首先遍历t,把每个字母出现的次数记录下来,然后开始遍历s,如果对应的映射值-1后还大于等于0,说明这个字符是我们需要且个数还不够的,也就是最后会出现在结果字符串里面的,因此我们将记录长度的变量cnt加1,表示我们新找到了一个符合目标的值,如果对应的映射-1小于等于0,那有两种情况,一种是这个字母就不是我们所需的,初值即为0,一减肯定小于0,这个就不影响结果了,另一种情况是这个字母是我们需要的,但我们前面已经遍历到了足够个数的字母,已经将其对应的映射值减为0了,这次继续减,不应该再增加长度变量cnt了,但是,我们仍然进行减操作,因为这里实际上把字母出现的个数给记录下来了,后面用得到。当cnt和t的长度相等时,说明我们已经累积了足够多的字母,于是开始进行滑动,我们用当前遍历的索引i和一个left指针来表示窗口大小,min_len和min_left表示动态更新的窗口大小和在此窗口大小下对应的左索引,如果此时i-left+1<min_len,表明我们可以更新min_len,同时更新min_left,否则不做任何操作,我们进行以上操作后,就开始考虑收缩窗口,但我们需要知道我们收缩的时候,跳过去的那个字母是不是我们所需要的值,因此我们将对应的映射值加一并进行判断(加一表示在窗口中去掉当前这个元素,因为上文中加入的时候是减一),如果加一后对应的值大于0,说明我们已经没有足够的字母了,因此我们将cnt减一,退出while(cnt=t.length())的循环,表示需要继续向右扩张,补充更多的元素,否则,说明去掉当前这个元素后,窗口中的字母个数依然是足够覆盖t字符串的,因此不做任何操作。遍历结束后,我们用min_left的值来判断是否中途有经过更新(min_left初始值为-1),如果没有,就返回空字符串,如果有,就在s中截取(min_left, min_left+min_len)这个区间返回。这里需要注意,java中String的substring用的是beginIndex和endIndex,而不是beginIndex和length,这个地方搞错了一次。

代码 t74 s84 java

class Solution {
    public String minWindow(String s, String t) {
        int min_left = -1, left = 0, min_len = Integer.MAX_VALUE, cnt = 0;
        int[] mp = new int[128];
        for(int i=0; i<t.length(); i++) mp[t.charAt(i)]++;
        for(int i=0; i<s.length(); i++){
            if(--mp[s.charAt(i)]>=0) cnt++;
            while(cnt==t.length()){
                if(i-left+1<min_len){
                    min_left = left;
                    min_len = i - left + 1;
                }
                if(++mp[s.charAt(left)]>0) cnt--;
                left++;
            }
        }
        return min_left == -1 ? "" : s.substring(min_left, min_left + min_len);
    }
}

参考资料
https://leetcode.com/problems/minimum-window-substring/solution/


程序员灯塔
转载请注明原文链接:76. 最小覆盖子串
喜欢 (0)