首页 > itarticle > leetcode “76. minimum window substring”

leetcode “76. minimum window substring”

admin 11月 13, 2020 0

LeetCode link

Intuition

  • Using two pointer to border the sliding window.
  • Using a map to save the count of each character appearance and a map to save the count of character in the window.

solution

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
 
class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        int[] expectCount = new int[256];
        int[] nowCount = new int[256];
        for (int i = 0; i < t.length(); i++) {
            expectCount[t.charAt(i)]++;
        }
        int minLength = Integer.MAX_VALUE;
        String result = "";
        int count = 0;
        for (int begin = 0, end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if (expectCount[c] <= 0) {
                continue;
            }
            nowCount[c]++;
            count++;
            if (count >= t.length()) {
                while (expectCount[s.charAt(begin)] <= 0 || nowCount[s.charAt(begin)] > expectCount[s.charAt(begin)]) {
                    if (nowCount[s.charAt(begin)] > expectCount[s.charAt(begin)]) {
                        count--;
                        nowCount[s.charAt(begin)]--;
                    }
                    begin++;
                }
                if (end - begin + 1 < minLength) {
                    result = s.substring(begin, end + 1);
                    minLength = end - begin + 1;
                }
            }
        }
        return result;
    }
}

problem

WA.

reason

When adding the count, it didn’t take consider of the duplicate chars, so maybe the count is greater or equal to the length of t, but maybe there’s some wrong case(such as window is [b,b] but t is [a,b]).

modification

Need to avoid the duplicate case.

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
 
class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        int[] expectCount = new int[256];
        int[] nowCount = new int[256];
        for (int i = 0; i < t.length(); i++) {
            expectCount[t.charAt(i)]++;
        }
        int minLength = Integer.MAX_VALUE;
        String result = "";
        int count = 0;
        for (int begin = 0, end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if (expectCount[c] <= 0) {
                continue;
            }
            nowCount[c]++;
            if (nowCount[c] <= expectCount[c]) {
                count++;
            }
            if (count >= t.length()) {
                while (expectCount[s.charAt(begin)] <= 0 || nowCount[s.charAt(begin)] > expectCount[s.charAt(begin)]) {
                    if (nowCount[s.charAt(begin)] > expectCount[s.charAt(begin)]) {
                        nowCount[s.charAt(begin)]--;
                    }
                    begin++;
                }
                if (end - begin + 1 < minLength) {
                    result = s.substring(begin, end + 1);
                    minLength = end - begin + 1;
                }
            }
        }
        return result;
    }
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能