LeetCode76. 最小覆盖子串

Yuyy

发布于 2022-06-28 20:20:29

24300

代码可运行

文章被收录于专栏：yuyy.info技术专栏yuyy.info技术专栏

运行总次数：0

代码可运行

本文最后更新于 510 天前，其中的信息可能已经有所发展或是发生改变。

一、思路

熟悉下滑动窗口算法，虽然能理解，但细节问题还是遇到很多。调试了很多遍才通过。最后个用例过不了，用例长度特别大，当时只想到是不是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
s 和 t 由英文字母组成

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

三、代码

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);
        }

Post Views: 280

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-2-03 1，如有侵权请联系 cloudcommunity@tencent.com 删除

uml