Problem: 76. 最小覆盖子串

思路

利用滑动窗口思想。right表示子串的最后一个位置，right不断右移，直到覆盖t中所有字符。此时left不断左移，移动过程中更新最小子串的值，直到不再满足条件，left停止移动。然后right向右移动，重复以上的步骤，直到right==n。其中left，right初始化为0。

怎么判断覆盖了t中所有字符呢？有两种方法。

  1. 利用map存储t中字符和对应的个数。每次更新right之后，更新map，循环调用isContainAll函数判断mp中是否所有键对应的值都小于等于0。如果是，说明已经覆盖了t中所有字符，可以更新结果。但利用map的话，每次循环调用isContainAll函数，时间复杂度会增加，最小是O(52∗m+n)O(52*m+n)O(52∗m+n)。
  2. 利用两个变量。required表示t中字符的种类数。matched表示已经包含的字符种类数。每次更新right时，根据条件更新matched，然后循环判断mathed是否等于required，不断更新结果。这样做，时间复杂度是O(m+n)O(m+n)O(m+n)。

利用方法1和2，实测运行时间缩短了10倍左右。

img

Tips：中间循环过程中调用substring会超出内存限制。因为自从jdk7起之后，substring函数执行时会在内存中生成原字符串的拷贝对象，每次调用substring，每次占用新的内存，对于字符串过长的场景，会超出内存限制。因此我们循环过程中利用begin和cnt记录最小字符串的起始坐标和大小，返回的时候再调用substring。

复杂度

  • 时间复杂度: O(m+n)
  • 空间复杂度: O(∣∑∣)，∑为哈希表长度，最大为52

Code

方法一：

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
48
/**中间循环过程中调用substring会超出内存限制 */
class Solution {
    public String minWindow(String s, String t) {
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        int m = sc.length;
        int n = tc.length;
        if(m < n){
            return "";
        }

        Map<Character,Integer> mp = new HashMap<>();
        for(char c : tc){
            mp.merge(c, 1, Integer::sum);
        }

        int cnt = Integer.MAX_VALUE;
        int left = 0;
        int begin = -1; // 记录最小字符串的起始坐标

        for(int right = 0; right < m; right ++){
            if(mp.containsKey(sc[right])){
                mp.merge(sc[right], -1, Integer::sum);
            }
           
            while(isContainAll(mp)){
                if(right - left + 1 < cnt){
                    cnt = right - left + 1;
                    begin = left;
                }
                if(mp.containsKey(sc[left])){
                    mp.merge(sc[left],1,Integer::sum);
                }
                left ++;
            }
        }
        return begin == -1 ? "" : s.substring(begin, begin+cnt);
    }

    private boolean isContainAll(Map<Character,Integer> mp){
            for(Character ch : mp.keySet()){
                if(mp.get(ch) > 0){
                    return false;
                }
            }
            return true;
    }
}

方法二：

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
48
49
class Solution {
    public String minWindow(String s, String t) {
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        int m = sc.length;
        int n = tc.length;
        if (m < n) {
            return "";
        }

        Map<Character,Integer> mp = new HashMap<>();
        int required = 0; //要匹配的字符种类数
        for(char c : tc){
            mp.merge(c, 1, Integer::sum);
            if (mp.get(c) == 1) {
                required ++;
            }
        }

        int cnt = Integer.MAX_VALUE;
        int left = 0;
        int begin = -1; // 记录最小字符串的起始坐标
        int matched = 0; // 已经匹配的字符种类数

        for(int right = 0; right < m; right ++) {
            if (mp.containsKey(sc[right])) {
                mp.merge(sc[right], -1, Integer::sum);
                if (mp.get(sc[right]) == 0) {
                    matched ++;
                }
            }
            while (matched == required) {
                if (right - left + 1 < cnt) {
                    cnt = right - left + 1;
                    begin = left;
                }
                if (mp.containsKey(sc[left])) {
                    mp.merge(sc[left],1,Integer::sum);
                    if (mp.get(sc[left]) == 1) {
                        matched --;
                    }
                }
                left ++;
            }
        }

        return begin == -1 ? "" : s.substring(begin, begin + cnt);
    }
}