C++ post referred to top voted post


  • 4

    First, thanks the post from @vinceyuan

    Here I just try explain it carefully so to help some beginners to better understand the inspiring ideas behind the solution.

    Preprocessing step:

    store the condition variable in the unordered_map

    While loop step:

       check sub-conditions, update global variable
    
       for the satisfying condition, we can move the start pointer 
       forward to calculate all the possible solution.
    

    I do think this solution is really not easy to us to implement all by our self.

    The only way to better grasp this solution is to write it many times by yourself.

    Here is the C++ implementation:

    class Solution {
    public:
        string minWindow(string s, string t) {
            vector<int> v(128, 0);
            for(auto c:t) v[c]++;
            int start=0, end=0, counter=t.size();
            int minStart=0, minLen=INT_MAX;
            int len=s.size();
            while(end<len){
                if(v[s[end]]>0)  counter--;
                v[s[end]]--;
                end++;
                while(counter==0){
                    if(end-start<minLen){
                        minStart=start;
                        minLen=end-start;
                    }
                    v[s[start]]++;
                    if(v[s[start]]>0)  counter++;
                    start++;
                }
            }
            if(minLen!=INT_MAX)
                return s.substr(minStart, minLen);
            return "";
        }
    };

  • 0

    This is the post I almost write all by myself.

    I realize that more details.

       v[s[end]]>0  means the char appears in t , so need to appear in s for same times.
    

    Here is the code.

    class Solution {
    public:
        string minWindow(string s, string t) {
            vector<int> v(128, 0);
            for(auto c:t) v[c]++;
            int start=0, end=0, counter=t.size();
            int m_start=0, m_len=INT_MAX;
            while(end<s.size()){
                if(v[s[end]]>0)  counter--;
                v[s[end]]--;
                end++;
                while(counter==0){
                    if(m_len>end-start){
                        m_start=start;
                        m_len=end-start;
                    }
                    v[s[start]]++;
                    if(v[s[start]]>0) counter++;
                    start++;
                }
            }
            if(m_len<INT_MAX)  
                return s.substr(m_start, m_len);
            else
                return "";
        }
    };

  • 0

    The difficulty may lay that the while loop in the while loop. Every time we meet a satisfied string, we need to update the "start" variable to find shorter result.


  • 0
    2

    In this solution

    I made the similiar mistakes ....

     use   dict[start]   but should use  dict[s[start]
    

    Also , we should include the case that the t not appears in s, meaning that the m_len is INT_MAX....

    2333333333333333

    Here is the code :

    class Solution {
    public:
        string minWindow(string s, string t) {
            int size_s = s.size(), size_t = t.size();
            vector<int> dict(128, 0);
            for(auto c : t)  dict[c]++;
            int start = 0, end = 0, count = 0;
            int m_len = INT_MAX, m_start = 0;
            while(end < size_s) {
                if(dict[s[end]] > 0) {
                    count++;   
                }
                dict[s[end]]--;
                end++;
                while(count >= size_t) {
                    if(end - start < m_len) {
                        m_start = start;
                        m_len = end - start;
                    }
                    dict[s[start]]++;
                    if(dict[s[start]] > 0)  count--;
                    start++;
                }
            }
            return m_len == INT_MAX ? "" : s.substr(m_start, m_len);
        }
    };

  • -2

  • 0
    9

  • 0
    9

  • 0
    B

    The process is same as mine, but the code is more concise


  • 1
    Z

    Haha, that's my idea initially. @vinceyuan made it more readable. ^ ^


  • 0
    V

    it's nearly impossible to think of this solution by myself.


Log in to reply
 

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