leetcode-minimum-window-substring

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/minimum-window-substring/

　　给你一个字符串S和字符串T，在S中找到最小的窗口包含所有T中的字符，并输出这个窗口

题目分析

　　利用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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
public class Solution {
    public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
            return "";
        }
        int lenS = s.length();
        int lenT = t.length();
        Map<Character, Integer> hash = new HashMap<Character, Integer>(); // hash统计t中的字符
        
        for (int i = 0; i < lenT; i++) {
            char c = t.charAt(i);
            if (hash.containsKey(c)) {
                hash.put(c, 1 + hash.get(c));
            } else {
                hash.put(c, 1);
            }
        }
        Map<Character, Integer> window = new HashMap<Character, Integer>();
        int left = -1; // 窗口左边界
        int right = 0; // 窗口右边界
        int wCount = 0; //窗口中包含T中字符的个数
        int minLeft = -1; //最小窗口左边界
        int minRight = -1; // 最小窗口右边界
        int minW = Integer.MAX_VALUE; //最小窗口大小
        // 先确定left的第一个位置，也就是s中第一个包含t中的字符
        for (int i = 0; i < lenS; i++) {
            if (hash.containsKey(s.charAt(i))) {
                left = i;
                break;
            }
        }
        if (left == -1) {
            return "";
        }
        while (right < lenS) {
            char cur = s.charAt(right);
            if (!hash.containsKey(cur)) {
                right++;
                continue;
            }
            if (window.containsKey(cur)) {
                window.put(cur, 1 + window.get(cur));
            } else {
                window.put(cur, 1);
            }
            if (window.get(cur) <= hash.get(cur)) {
                wCount++;
            }
            if (wCount == lenT) { // 发现了一个可行的
                if (right - left + 1 < minW) {
                    minLeft = left;
                    minRight = right;
                    minW = right - left + 1;
                }
                // update left
                while (left < right) { // 窗口左边界也要右移
                    char l = s.charAt(left);
                    if (hash.containsKey(l)) {
                        if (window.get(l) <= hash.get(l)) {
                            wCount--;
                        }
                        window.put(l, window.get(l) - 1);
                    }
                    left++;
                    if (wCount < lenT) {
                        while (left < right && !hash.containsKey(s.charAt(left))) {
                            left++;
                        }
                        break;
                    } else { // 窗口在变小，因此也要更新答案。
                        if (right - left< minW) {
                            minLeft = left;
                            minRight = right;
                            minW = right - left + 1;
                        }
                    }
                }
            }
            right++;
        }
        if (minLeft != -1 && minRight != -1) {
            return s.substring(minLeft, minRight + 1);
        }
        return "";
    }
}