> LeetCode76. 最小覆盖子串 - Yuyy
Yuyy
Yuyy
LeetCode76. 最小覆盖子串

一、思路

熟悉下滑动窗口算法,虽然能理解,但细节问题还是遇到很多。调试了很多遍才通过。
最后个用例过不了,用例长度特别大,当时只想到是不是Integer溢出,但是又没报错。那个用例大得都复制不了,无赖只能看题解。
原来是Integer比较时用了==,前面的用例为啥通过了?因为Integer缓存[-128-127]。

二、题目

给你一个字符串 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
  • st 由英文字母组成

 

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

Related Topics
  • 哈希表
  • 双指针
  • 字符串
  • Sliding Window
  • \n

  • 👍 930
  • 👎 0
  • 三、代码

    public String minWindow(String s, String t) {
                Map<Character, Integer> needs = new HashMap<>();
                Map<Character, Integer> window = new HashMap<>();
                for (char c :
                        t.toCharArray()) {
                    needs.put(c, needs.get(c) == null ? 1 : needs.get(c) + 1);
                }
                int left = 0;
                int right = 0;
                int valid = 0;
                int start = 0;
                int length = Integer.MAX_VALUE;
                while (right < s.length()) {
                    char c = s.charAt(right++);
                    if (needs.containsKey(c)) {
                        window.put(c, window.get(c) == null ? 1 : window.get(c)+1);
                        if (window.get(c).equals(needs.get(c))) {
                            valid++;
                            while (valid==needs.size()) {
                                if (length > right - left) {
                                    length = right - left;
                                    start = left;
                                }
                                char c1 = s.charAt(left++);
                                if (window.containsKey(c1)) {
                                    if (window.get(c1).equals(needs.get(c1))) {
                                        valid--;
                                    }
                                    window.put(c1, window.get(c1) - 1);
                                }
                            }
                        }
                    }
                }
                return length == Integer.MAX_VALUE ? "" : s.substring(start,start +length);
            }
    

    发表评论

    textsms
    account_circle
    email

    Yuyy

    LeetCode76. 最小覆盖子串
    一、思路 熟悉下滑动窗口算法,虽然能理解,但细节问题还是遇到很多。调试了很多遍才通过。 最后个用例过不了,用例长度特别大,当时只想到是不是Integer溢出,但是又没报错。那个用例大…
    扫描二维码继续阅读
    2021-02-03
    友情链接
    标签
    归档
    近期文章
    分类
    近期文章