Written Examination Of SenseTime

Author Avatar
Xin Wei 4月 10, 2017
  • 在其它设备中阅读本文章

Minimum Window Substring

Minimum Window Substring

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 emtpy string “”.

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

这道题的要求是要在O(n)的时间度里实现找到这个最小窗口字串,那么暴力搜索Brute Force肯定是不能用的,我们可以考虑哈希表,其中key是T中的字符,value是该字符出现的次数。

  • 我们最开始先扫描一遍T,把对应的字符及其出现的次数存到哈希表中。

  • 然后开始遍历S,遇到T中的字符,就把对应的哈希表中的value减一,直到包含了T中的所有的字符,纪录一个字串并更新最小字串值。

  • 将子窗口的左边界向右移,略掉不在T中的字符,如果某个在T中的字符出现的次数大于哈希表中的value,则也可以跳过该字符。

#include <vector>
#include <iostream>
#include <string>
#include <climits>

using namespace std;

#define ALPHA_NUM 256

class Solution
{
    public:
        string minimumWindowSubstring(const string &S, const string &T)
        {
            if (S.length() < T.length()) return "";
            vector<int> T_dict(ALPHA_NUM, 0), S_dict(ALPHA_NUM, 0);
            for (char ch : T)
                T_dict[ch]++;
            int left = 0, count = 0, minLen = INT_MAX;
            string rst;
            for (int right = 0; right < S.size(); ++right)
            {
                if (T_dict[S[right]] > 0)
                {
                    S_dict[S[right]]++;
                    if (S_dict[S[right]] <= T_dict[S[right]]) count++;
                    while (count == T.size())
                    {
                        if (right - left + 1 < minLen)
                        {
                            minLen=right-left+1;
                            rst = S.substr(left, minLen);
                        }
                        // 如果遇左边界的字符出现在T中
                        if (T_dict[S[left]] > 0)
                        {
                            // 窗口中该字符出现次数减一
                            S_dict[S[left]]--;
                            // 如果现在窗口中的字符已经不能组成T,则减少计数器,循环结束,向后继续寻找新的字符加入窗口
                            if (S_dict[S[left]] < T_dict[S[left]]) count--;
                        }
                        left++;
                    }
                }
            }
            return rst;
        }
};

int main(int argc, char**argv)
{
    Solution s;
    string S, T;
    while(cin >> S >> T)
    {
        cout << s.minimumWindowSubstring(S, T) << endl;
    }
    return 0;
}

扫描线

#include <unordered_map>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

class Solution
{
    public:
        int scanLine(const vector<pair<int, int>> inputs)
        {
            vector<pair<int, bool> > nodes;
            for (int i = 0; i < inputs.size(); ++i)
            {
                nodes.push_back(make_pair(inputs[i].first, true));
                nodes.push_back(make_pair(inputs[i].second, false));
            }
            sort(nodes.begin(), nodes.end());
            int maxNum = 0, tmp = 0;
            for (int i = 0; i < nodes.size(); ++i)
            {
                if (nodes[i].second)
                {
                    tmp++;
                    if (tmp > maxNum)
                        maxNum = tmp;
                }
                else
                    tmp--;
            }
            return maxNum;
        }
};

int main()
{
    int n;
    int l, r;
    Solution s;
    while(true)
    {
        vector<pair<int, int> > inputs;
        cin >> n;
        for (int i = 0; i < n; ++i)
        {
            cin >> l >> r;
            inputs.push_back(make_pair(l, r));
        }
        cout << s.scanLine(inputs) << endl;
    }
    return 0;
}