【LeetCode 76】最小覆盖子串

【题解】

尺取法。
用l和r代表一个合法的覆盖子串。
我们不断地扩大右指针。
直到l..r包含T中的所有字母为止(重复的就要两次以上。)
然后我们可以尝试的让l++.
看看新的l..r是不是还是包含所有的字母。
如果是的话。
显然我们得到了一个更优的解。
而且可以肯定。
我们在递增l的时候
不会漏掉比当前更好的解。
因为如果l可以递增缺不递增。
那么从那个位置开始的最短的子串也只能到达r而已。
不会比l递增之后的结果更优。
因此这个算法是成立的。
判断是否包含所有的字母。
只要用个map来存储每个字母出现的次数就好了。(T字符串中的字母)
然后当r递增的时候。
令map[s[r]]--
如果让s[r]递减的时候第一次变成了0
就说明[l..r]这一段s[r]这个字母出现的次数已经满足了要求。

【代码】

class Solution {

public:

    string minWindow(string s, string t) {

        map<char,int> dic;dic.clear();

        int goal = 0;

        for (int i = 0;i<(int)t.size();i++) {

            dic[t[i]]++;

            if (dic[t[i]]==1) goal++;

        }

        int l = 0;int cnt = 0;

        int ll = -1,rr=-1;

        for (int r = 0;r<(int)s.size();r++){

            dic[s[r]]--;

            if (dic[s[r]]==0) cnt++;

            if (cnt==goal){

                while((l+1)<=r){

                    if (dic[s[l]]<0){

                        dic[s[l]]++;

                    }else break;

                    l++;

                }

                if (ll==-1){

                    ll = l,rr = r;

                }else{

                    if (rr-ll+1>r-l+1){

                        ll = l;rr = r;

                    }

                }

            }

        }

        string anss = "";

        for (int i = ll;i<=rr;i++){

            anss = anss + s[i];

        }

        return anss;

    }

};

巴特西

【LeetCode 76】最小覆盖子串

最新文章

热门文章