leetcode76-最小覆盖子串

原题

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

示例:

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

说明:

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

解法

思想

滑动窗口,用一个hashmap存储原字符串中字符的出现个数,再用一个hashmap存储滑动窗口内目标字符的出现个数,用一个变量记录滑动窗口内有多少个字符满足条件了。

代码

class Solution {
    public String minWindow(String s, String t) {
        int left = 0, right = 0;
        int start = 0, end = Integer.MAX_VALUE;
        Map<Character, Integer> window = new HashMap();
        Map<Character, Integer> needMap = new HashMap();
        for(int i = 0; i < t.length(); i++) {
            needMap.put(t.charAt(i), needMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int match = 0;
        while(right < s.length()) {
            char rightTemp = s.charAt(right);
            if(needMap.containsKey(rightTemp)) {
                int newCount = window.getOrDefault(rightTemp, 0) + 1;
                window.put(rightTemp, newCount);
                if(newCount == needMap.getOrDefault(rightTemp, 0)){
                    match++;
                }
            }
            right++;
            while(match == needMap.size()) {
                if(right - left < end - start) {
                    start = left;
                    end = right;
                }
                char leftTemp = s.charAt(left);
                if(needMap.containsKey(leftTemp)) {
                    window.put(leftTemp, window.getOrDefault(leftTemp, 0) - 1);
                    if(window.getOrDefault(leftTemp, 0) < needMap.getOrDefault(leftTemp, 0)) {
                        match--;
                    }
                }
                left++;
            }
        }
        return end == Integer.MAX_VALUE ? "" : s.substring(start, end);
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode76-%e6%9c%80%e5%b0%8f%e8%a6%86%e7%9b%96%e5%ad%90%e4%b8%b2/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月22日
下一篇 2020年5月23日

相关推荐

  • leetcode453-最小移动次数使数组元素相等

    原题 给定一个长度为 n 的非空整数数组,找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1。 示例: 输入: [1,2,3] 输出: 3 解释: 只…

    算法 2020年6月7日
    0140
  • leetcode374-猜数字大小

    原题 我们正在玩一个猜数字游戏。 游戏规则如下:我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了,我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接…

    算法 2019年12月31日
    0370
  • leetcode124-二叉树中的最大路径和

    原题 给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1…

    算法 2020年4月26日
    0170
  • leetcode403-青蛙过河

    原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单…

    算法 2020年6月16日
    04620
  • 海量数据-两种方法解决top k问题

    假如提供一百万个数据(甚至更大)的无序数组,如何从中获取最大的k个元素? 最容易想到的是先降序排序然后获取前k个元素,那假设我们用最常用的O(nlogn)级别的排序算法,要获取to…

    2020年4月4日
    0230
  • leetcode234-回文链表

    原题 请判断一个链表是否为回文链表。 示例1: 输入: 1->2 输出: false 示例2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂…

    2019年12月16日
    0110
  • leetcode705-设计哈希集合

    原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说,你的设计应该包含以下的功能 add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合…

    算法 2019年12月18日
    0140
  • 数组元素左右两边最近较小元素

    原题(来源牛客网) 给定一个不含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。 实例: 输入: ar…

    算法 2020年4月26日
    0700
  • leetcode290-单词规律

    原题 https://leetcode.cn/problems/word-pattern/description/ 解法 类似leetcode205-同构字符串 func word…

    算法 2024年3月26日
    050
  • leetcode20-有效的括号

    原题 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序…

    算法 2019年12月11日
    0220

发表回复

登录后才能评论