[567. Permutation in String] C++_9ms_AC_Vector


  • 0

    We use vector to store the chars information in s1, and if there is no such char in s1, set the value of vector[i] = -1.

    class Solution {
    public:
    bool checkInclusion(string s1, string s2) {
        vector<int> check(26, 0);
        for(auto s:s1){
            check[s - 'a']++;
        }
        for(auto c : check){
            c = (c == 0 ? -1 : c);
        }
        int n = 0, p = 0, q = 0;
       //n: count the matched length.
      //p and q: point to the start and current points at s2
        while(q < s2.size()){
            if(n == s1.size()) break;
            int t = s2[q] - 'a';
            if(check[t] >= 1){
                check[t]--;
                n++;
                q++;
            }else if(check[t] == 0){
            //check[t] == 0 means that the char exists in s1
            //so we need to find the first char: s2[q] which appears between p and q, 
            //also remember to recover the count vector, check.
                while(p < q  && s2[p] != s2[q]){
                    check[s2[p] - 'a']++;
                    p++;
                    n--;
                }
                //at: s2[p] == s2[q]
                check[s2[p] - 'a']++;
                p++;
                n--;
            }else{//check[t] == -1, not exist in s1
             //check[t] == -1 means that the current char, s2[q], does not exist in s1
             //so we need to re-start our search.
                while(p < q){
                    check[s2[p] - 'a']++;
                    p++;
                }
                q = ++p;
                n = 0;
            }
            
        }
        return n == s1.size();
    }
    };

Log in to reply
 

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