leetcode 76最小覆盖子串

time O(n) spaceO(n) 的方法：

还是借助哈希表，所有字母初始化为0，将t中出现的所有字母次数全都记录在哈希表里；

采用双指针，分别为一个头指针head,和尾指针tail。flag记录当前[head,tail)没有出现的字母的个数；

　　1. flag不为0时，更改s[tail]的哈希值，即h[s[tail]]--;在t中没有出现的字符哈希值会被减为负数，所以如果h[s[tail]]>=0,那么当前值在t中出现过，flag--；最后向右延伸tail，tail++；

　　2. 可知flag为0时，t中所有的字母都已经在[head,tail)中出现，因此可以比较并记录当前结果的起始位置start和长度len，并且尝试从head缩短当前的子串；

　　h[s[head]]++;之后，只有在t中出现的字母哈希值可能大于0，没有出现的一定小于等于0；如果是t中出现的（即 h[s[head]]>0），则令flag++，类似于出栈的操作；最后向右移动head，即head++;

总之是借哈希表，通过双指针和flag，维护一个window，

class Solution {

public:

    string minWindow(string s, string t) {

        //将是否已经出现全部的t作为判断条件，如果没有，则不断的增加尾部;如果已经满足，则增加头部；time O(n),space O(n)

        int ls=s.size(),lt=t.size();

        if( ls ==  || lt ==  ) return "";

        vector<int> h(, );

        for(auto c:t)

            h[c]++;

        int head=,tail=,start=,len=INT_MAX;

        int flag=lt;//>0移动末尾，等于0移动head;

        while(head<ls && tail<=ls){

            if(flag){

                if(tail==ls) break;

                h[s[tail]]--;//所有字母都--，那么之后执行++时未出现在t中的字母一定不会超过0；

                if(h[s[tail]]>=) flag--;

                tail++;

            }else{

                if(tail-head<len){

                    start=head;

                    len=tail-head;

                }

                h[s[head]]++;

                if(h[s[head]]>) flag++;//对应所有字母都--的操作

                head++;

            }

        }

        return len==INT_MAX? "":s.substr(start,len);

    }

};

下面方法有2个测试样例超时 time O(n2) space O(n)

class Solution {

public:

    string minWindow(string s, string t) {

        //time O(n2) space O(1);

        int len=s.size(),k=t.size();

        int tail=-,lon=-;

        string res=s;

        for(int i=k-;i<len;i++){

            int j=i;

            multiset<int> h(t.begin(),t.end());

            while(j>=){

                if(h.count(s[j])) h.erase(h.find(s[j]));

                if(h.size()==){

                    if(lon< || lon>i-j+) {lon=i-j+;tail=i;}

                    break;

                }

                j--;

            }

        }

        if(tail==-) return "";

        res=s.substr(tail-lon+,lon);

        return res;

    }

};

巴特西

leetcode 76最小覆盖子串

最新文章

热门文章