c++ o(n) hash table


  • 0
    B
    class Solution {
    private:
        int left = 0;
        int right = 0;
        int begin = 0;
        int end = 0;
        int tmp = INT_MAX;
        vector<int> needfound = vector<int>(128,0);
        vector<int> isfound = vector<int>(128,0);
    public://author:qiuqian
        string minWindow(string s, string t) {
            for(auto &x:t) needfound[x]++;
            int count = t.size();
            isfound[s[0]]++;
            if(needfound[s[0]] >= isfound[s[0]]) count--;
            while(1){
                if(count == 0){
                    while(isfound[s[begin]] > needfound[s[begin]]){
                        isfound[s[begin]]--;
                        begin++;
                    }
                    int len = end-begin+1;
                    if(len < tmp){
                        right = end;
                        left = begin;
                        tmp = len;
                    }
                }
                if(end < s.size()){
                    end++;
                    isfound[s[end]]++;
                    if(needfound[s[end]] >= isfound[s[end]]) count--;
                }else break;
            }
            if(tmp == INT_MAX) return "";
            else return s.substr(left,tmp); 
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.