567. Permutation in String

一開始一直用暴力去寫, 就是測試所有permute, 太久了會超時

class Solution {
public:
    bool permute_str(string &s1, string cur, vector<bool> visited, string &s2){
        if(cur.size() == s1.size()){
auto it = s2.find(cur);
            if(it != string::npos){
                return true;
            }
            return false;
        }
        for(int i = 0; i < s1.size();i++){
            if(visited[i]) continue;
            visited[i] = true;
            if(permute_str(s1, cur + s1[i], visited, s2)){
                return true;
            }
            visited[i] = false;
        }
        return false;
    }
    bool checkInclusion(string s1, string s2){
        vector<bool> visited(s1.size(), false);
        if(permute_str(s1, "", visited, s2)){
            return true;
        }
      
        return false;
    }
};

要用sliding windows

蠻聰明的作法XD

class Solution {
public:
   
    bool checkInclusion(string s1, string s2){
        vector<int> count1(26, 0);
        vector<int> count2(26, 0);
        for(int i = 0 ; i < s1.size();i++){
            count1[s1[i] - 'a']++;
        }
        int l = 0;
        int r = 0;
        while(r < s2.size()){
            count2[s2[r] - 'a']++;
            if(count1 == count2) return true;
            r++;
            
            while( r - l > s1.size() - 1){
                count2[s2[l] - 'a']--;
                l++;
            }
        }
        if(count1 == count2) return true;
        return false;
    }
};