567. Permutation in String

Sliding Windowを用いた方法

1. s1をソート

2. sliding window法を用いて、s1の長さ分だけs2の文字をソートしていく

https://leetcode.com/problems/permutation-in-string/discuss/1385457/Very-Easy-C%2B%2B-Solution

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if(s1.length() > s2.length() ){
            return false;
        }
        
        sort(s1.begin(), s1.end());
        
        for(int i= 0; i<s2.length()-s1.length()+1; i++){
            
            string tmp = s2.substr(i, s1.length());
            
            sort(tmp.begin(),tmp.end());
            if(s1 == tmp){
                return true;
            }
        }
        return false;
    }
};

1. s1の各文字の個数を算出

2. sliding window法を持ちいて、s2の各文字の個数を算出し同じならtrue

1.cur[s2[i - s1.size()] - 'a']--;の意味 s2ではs1の文字数だけを見たいので、3 Input: s1 = "ab", s2 = "eidbaooo"ならば、idのところに来たらeを消す

https://leetcode.com/problems/permutation-in-string/discuss/638833/C%2B%2B(Simple-using-Sliding-Window)

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> cur(26), goal(26);
        for(char c : s1){
            goal[c - 'a']++;
        }
        
        for(int i = 0; i < s2.size(); i++) {
            cur[s2[i] - 'a']++;
            if(i >= s1.size()) {
                cur[s2[i - s1.size()] - 'a']--;
            }
            
            if(goal == cur){
                return true;
            } 
        }
        return false;
    }
};