题意分析

  • 给出两个字符串S和T，需要我们在S字符串里面找到一个最短的字符串，使得这个这个字符串中包含T字符串里面的所有的字符。题目要求使用O(n)的时间复杂度。题目一定保证如果存在这个字符串，那么这个字符串一定是唯一的。

思路分析

解法一 二分查找

  • 我们看到求最短的字符串，那么很容易可以想到用二分的方法进行求解。我们对这个字符串的长度进行二分，显然，这个答案是有单调性的，如果存在长度为x的字符串满足条件，那么一定存在长度超过x的字符串满足条件。然后就是一个judge函数的写法了，这里我是直接用一个unordered_map存储T字符串的字符的个数，用一个unordered_map存储枚举的字符串的个数，然后遍历T字符串做一个对比。

  • 代码如下

    • 二分的时间复杂度为O(logn),对每个二分的结果进行判断的时间复杂度为O(n^2)，所以最后的时间复杂度为O(n^2logn)
    • 这里需要对字符串中的字符的个数进行哈希，所以空间复杂度为O(n) 
class Solution {
public:
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    unordered_map<char,int> mp;

    // 判断是否存在长度为len的子串满足题目的条件
    string judge(string s,string t,int len){
        unordered_map<char,int> tmp;
        for(int i=0;i+len-1<s.size();i++){
            tmp.clear();
            for(int j=i;j<i+len;j++){
                tmp[s[j]]++;
            }
            bool flag=true;
            // 如果这个子串的每个字符的哈希个数小于这个字符串的哈希个数，那么直接退出
            for(auto c:t){
                if(mp[c]>tmp[c]){
                    flag=false;
                    break;
                }
            }
            if(flag){
                // 如果这个字符串满足题目的条件，那么直接将这个字符串返回
                string tmp="";
                for(int j=i;j<i+len;j++){
                    tmp+=s[j];
                }
               // std::cout<<"tmp:"<<tmp<<endl;
                return tmp;
            }
        }
        return "";
    }
    string minWindow(string S, string T) {
        // write code here
        if(S.size()==T.size()){
            return S==T?S:"";
        }
        for(auto c:T){
            mp[c]++;
        }
        string res="";
        int l=T.size(),r=S.size(),mid;
        // 对最终的答案的长度进行二分操作
        while(l<r){
            mid=(l+r)>>1;
            string tmp=judge(S,T,mid);
           // std::cout<<tmp<<endl;
            if(tmp!=""){
                r=mid;
                res=tmp;
            }else{
                l=mid+1;
            }
        }
        //std::cout<<r<<endl;
        return res;
    }
};

解法二 双指针

  • 显然，上面的解法其实是不符合题目的要求的，所以我们就需要继续寻找更优的解法。从上面的二分的情况我们可以看到，其实在枚举长度的时候，我们有很多都是浪费了的。根本没必要进行继续枚举，而是可以跳过一部分。所以，我们找到了双指针的写法。双指针就是利用两个指针的移动维护我们想要维护的值。

图片说明

  • 在这个题目中，当我们进行双指针维护的时候，右指针移动的条件是当前这个序列还是不符合题目的条件，如果一旦符合题目的要求，右指针停止移动，左指针移动一步。

  • 代码如下

    • 双指针只需要对字符串扫一遍就行，时间复杂度为O(n)
    • 还是需要使用unordered_map进行哈希，空间复杂度为O(n) 
class Solution {
public:
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    // judge判断当前的局面是否满足题目的要求，满足返回true
    bool judge(string t,unordered_map<char,int> mp1,unordered_map<char,int> mp2){
        for(auto c:t){
            if(mp1[c]>mp2[c]) return false;
        }
        return true;
    }
    string minWindow(string S, string T) {
        // write code here
        unordered_map<char,int> mp1,mp2;
        for(auto c:T){
            mp1[c]++;
        }
        int n=S.size();
        string ans="";
        int mi=1e9;
        for(int l=0,r=0;l<n;l++){
            // 如果右指针比左指针小，同时右指针每到边界，而且此时还没有到达题目要求
            while(l<=r&&r<n&&!judge(T,mp1,mp2)){
                mp2[S[r]]++;
                r++;
            }
            // 出来的时候也要判断，因为可能存在右指针到了边界，光左指针进行移动的情况
            if(judge(T,mp1,mp2)==false) continue;
            int len=r-l+1;
            // 维护最小的子串
            if(mi>len){
                mi=len;
                ans="";
                for(int i=l;i<r;i++){
                    ans+=S[i];
                }
            }
            mp2[S[l]]--;
        }
        return ans;
    }
};