首页 > itarticle > leetcode 76. minimum window substring

leetcode 76. minimum window substring

admin 11月 12, 2020 0

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).

For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.

Note:
If there is no such window in S that covers all characters in T, return the empty string “”.

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Solution:

这道题的思路我自己没有想到，看了discuss大佬的解法，才明白了一些，这类题的解法和前面的Largest Rectangle in Histogram和Longest Substring Without Repeating Characters有一点类似，都是维护两个指针，找到一个解以后去尝试有没有更好的解，直到遍历完所有的数据。

具体的可以看代码实现：

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
 
string (string s, string t) 
{
    vector<int> table_t(256, 0);
    for (auto c : t)
        ++table_t[c];
    
    int start = 0, end = 0, min_start = 0, min_len = INT_MAX;
    
    int counter = t.size();
    
    while (end < s.size())
    {
        // If char in s exists in t, decrease counter
        if (table_t[s[end]] > 0)
            --counter;
        // if a char s[end] is not in t, table_t[s[end]] will be negative.
        --table_t[s[end]];
        ++end;
        // When we found a valid window, move start to find smaller window.
        while (counter == 0)
        {
            if (end - start < min_len)
            {
                min_start = start;
                min_len = end - start;
            }
            
            ++table_t[s[start]];
            // // When char exists in t, increase counter.
            if (table_t[s[start]] > 0)
                ++counter;
            
            ++start;
        }
    }
    
    if (min_len != INT_MAX)
        return s.substr(min_start, min_len);
    else
        return "";
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能