LeetCode76-最小覆盖字串

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/minimum-window-substring/

中文链接：https://leetcode-cn.com/problems/minimum-window-substring/

题目详述

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

示例：

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

说明：

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

题目详解

滑动窗口。

因为是求满足条件的最小字串，不能运用 LeetCode438-找到字符串中所有字母异位词 的固定窗口大小的做法，只能采取求满足条件的最小窗口大小的方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class LeetCode_00076 {

    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        int[] map = new int[128];
        for (char c : t.toCharArray()) {
            ++map[c];
        }
        int size = t.length();
        int l = 0, r = 0;
        int resL = 0, resR = Integer.MAX_VALUE;
        while (r < s.length()) {
            if (--map[s.charAt(r++)] >= 0) {
                --size;
            }
            while (size == 0) {
                if (r - l < resR - resL) {
                    resL = l;
                    resR = r;
                }
                if (++map[s.charAt(l++)] > 0) {
                    ++size;
                }
            }
        }
        return resR == Integer.MAX_VALUE ? "" : s.substring(resL, resR);
    }
}

也可以运用 HashMap 来记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class LeetCode_00076 {

    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        Map<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int size = t.length();
        int l = 0, r = 0;
        int resL = 0, resR = Integer.MAX_VALUE;
        while (r < s.length()) {
            char c = s.charAt(r++);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                if (map.get(c) >= 0) {
                    --size;
                }
            }
            while (size == 0) {
                if (r - l < resR - resL) {
                    resL = l;
                    resR = r;
                }
                c = s.charAt(l++);
                if (map.containsKey(c)) {
                    map.put(c, map.get(c) + 1);
                    if (map.get(c) > 0) {
                        ++size;
                    }
                }
            }
        }
        return resR == Integer.MAX_VALUE ? "" : s.substring(resL, resR);
    }
}