Leetcode(76) Minimum Window Substring

发表于 | 分类于

Description

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

1
2
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

解法

因为时间复杂度限制在了O(n)，因此只能通过至少一次遍历字符串实现，当时想到了应该利用哈希做题，具体思路为：用一个哈希表记录t中字符剩下的需要出现的次数（对于给定范围的字符串而言即s[start,i]），为负数时说明多出现了几次，用变量num记录给定范围字符串中还缺少多少个t中的字母，那么，当num为0时即找到一个符合条件的字符串。整体思路为先把所有的Ｔ中的字符找到，然后从左端缩减这个字符串，直到不能完全包含Ｔ，是一个经典的滑动窗口题

具体代码如下：

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
39
40
41
42
43
44
45
46
47
class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> hsmap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            if (hsmap.containsKey(t.charAt(i))) {
                int tmp = hsmap.get(t.charAt(i));
                hsmap.replace(t.charAt(i), tmp + 1);
            } else {
                hsmap.put(t.charAt(i), 1);
            }
        }
        int num = t.length();
        int len = Integer.MAX_VALUE;
        int start = 0;
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            //根据左边界确定右边界，i起到了右边界的作用
            if (hsmap.containsKey(s.charAt(i))) {
                int tmp = hsmap.get(s.charAt(i));
                if (tmp > 0) {
                    num--;
                }
                hsmap.replace(s.charAt(i), tmp - 1);
            }
            //右边界确定，进入while循环，右移左边界，tmp只能为负或为0，为负数时说明可以继续右移左边界
            while (num == 0) {
                if (i - left + 1 < len) {
                    len = i - left + 1;
                    start = left;
                }
                if (hsmap.containsKey(s.charAt(left))) {
                    int tmp = hsmap.get(s.charAt(left));
                    if (tmp == 0) {
                        num++;
                    }
                    hsmap.replace(s.charAt(left), tmp + 1);
                }
                left++;
            }
        }
        if (len == Integer.MAX_VALUE) {
            return "";
        } else {
            return s.substring(start, start + len);
        }
    }
}