Permutation in String

1.解析 

题目大意，判断字符串s1（不考虑其顺序）是否是s2的子串。

2.分析

这道题最简单的办法无非就是利用系统提供的next_permutation函数，该函数提供字符串排序的功能，这样就可以不用考虑s1的顺序，每次求解下一个排列，然后s2字符串直接判断是否是其子串即可。这里要特别注意next_permutation函数，如果不理解，可以具体查看它的源码。但这种方法的时间复杂度很高，当s1字符串的长度超过20，进行全排序会耗掉大量的时间，更不用说100以上啦，所以肯定会TTL(时间超时)。

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.size() > s2.length()) return false;
        string org_s1 = s1;
        while (true){
            if (s2.find(s1) != string::npos) return true;  
            next_permutation(s1.begin(), s1.end()); //求解下一个排列
            if (org_s1 == s1) break;
        }
        return false;
    }
};

 上述方法行不通，一般求解连续子串使用滑动窗口无非是最好的。我们可以维持一个n大小的窗口，首先用hashtable统计字符串s1每个字符出现的个数(方便查找)，然后，遍历s2字符串，主要分为以下两种情况：

①s2字符串当前的字符不属于s1字符串：重置窗口大小为n，并重置hashtable

②s2字符串当前的字符属于s1字符串：(1)匹配字符的个数已经为0：向右滑动窗口，恢复待匹配的字符个数，直到碰到当前匹配的字符 (2)匹配字符的个数 > 0：当前窗口大小减1，待匹配的字符减1

具体实现如下：

class Solution {
public:
    bool checkInclusion(string s1, string s2){
        unordered_map<char, int> ch_to_val, c_ch_to_val;
        for (auto ch : s1) ch_to_val[ch]++;
        c_ch_to_val = ch_to_val;
        int n = s1.size(), m = s2.size(); //n为滑动窗口大小
        bool flag = true;
        int start;
        for (int i = 0; i < m; ++i){
            if (ch_to_val.count(s2[i])){
                if (ch_to_val[s2[i]] > 0){
                    if (flag){
                        start = i; //记录起始位置
                        flag = false;
                    }
                    if (--n <= 0) return true;
                    ch_to_val[s2[i]]--;
                }
                else{
                    for (; s2[start] != s2[i]; ++start){
                        n++;
                        ch_to_val[s2[start]]++; //重新计数
                    }
                    start++;
                }
            }
            else{ //重新匹配窗口
                ch_to_val.clear();
                ch_to_val = c_ch_to_val;
                n = s1.size();
                flag = true;
            }
        }
        
        return false;
    }
};

下面这种解法是对上面算法的优化，参考Grandyang博主的思路，其实我想复杂啦。用数组记录s1字符串每个字符出现的个数，借助左右指针，左指针代表窗口的左边界，右指针代表窗口的右边界。在遍历字符串s2的过程中，如果当前字符在待匹配字符数组中，则判断当前窗口的大小是否等于s1字符串的大小，如果等于，则满足条件；若当前字符不在待匹配字符数组，则要么是该字符不存在字符串s1要么待匹配字符已经匹配完，则往左滑动窗口，并恢复之前匹配过的字符的个数，直到当前字符的计数为0。之所以将数组大小设置为123，主要是因为字符'z'对应的ASCII为122。具体实现如下：

class Solution {
public:
    bool checkInclusion(string s1, string s2){
        vector<int> val(123, 0);
        int n = s1.size(), left = 0; //left是左边界
        for (auto ch : s1) val[ch]++;
        for (int right = 0; right < s2.size(); ++right){ //右边界
            if (--val[s2[right]] < 0){
                while (++val[s2[left++]] != 0);
            }
            else if (right - left + 1 == n) return true; //判断窗口大小
        }
        
        return false;
    }
};

下面这种解法也是来自Grandyang博主，使用双数组，不借助双指针。思路比较简单，具体实现如下： 

class Solution {
public:
    bool checkInclusion(string s1, string s2){
        vector<int> m1(123, 0), m2(123, 0);
        int n1 = s1.size(), n2 = s2.size();
        for (int i = 0; i < n1; ++i){
            m1[s1[i]]++;
            if (i < n2) m2[s2[i]]++;
        }
        if (m1 == m2) return true;
        for (int i = n1; i < n2; ++i){
            ++m2[s2[i]];
            --m2[s2[i-n1]];
            if (m1 == m2) return true;
        }
        
        return false;
    }
};