567.Permutation in String

Tags: Sliding Window Medium Two Pointers

Links: https://leetcode.com/problems/permutation-in-string/

---

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Example 1:

Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

1. The input strings only contain lower case letters.
2. The length of both given strings is in range [1, 10,000].

---

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (s2.size() < s1.size()) return false;

        vector<int> m(26);
        for (int i = 0; i < s1.size(); ++i) {
            ++m[s1[i] - 'a'];    
        }

        vector<int> tmp(26);
        int len = s2.size();
        int start = 0, end = s1.size() - 1;
        for (int i = start; i <= end; ++i) {
           ++tmp[s2[i] - 'a']; 
        }
        if (judge(m, tmp)) return true;

        while (++end < len) {
            ++tmp[s2[end] - 'a'];
            --tmp[s2[start++] - 'a'];
            if (judge(m, tmp)) return true;
        }

        return false;
    }

    inline bool judge(const vector<int> & v1, const vector<int> & v2)
    {
        for (int i = 0; i < 26; ++i) {
            if (v1[i] ^ v2[i]) return false;
        }

        return true;
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Permutation in String.
Memory Usage: 9.7 MB, less than 50.00% of C++ online submissions for Permutation in String.

尺取法。让在s2内的[start, end]区间长度和s1相同，如果是一个全排列，那么必然包含相同的字母以及数量，因为只有小写字母，那么就维护一个长度为26的数组即可。每次只需比较数组是否完全相同即可。

每次让数区间向后移动一个单位，并判断，时间复杂度$O(l1+26*(l2-l1))$。空间复杂度，因为为常数26，所以空间复杂度是$O(1)$。

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<int> pattern(26, 0), text(26, 0);
        for (auto &e : s1) ++pattern[e - 'a'];

        int m = s1.size(), n = s2.size();
        if (n < s1.size()) return false;
        for (int i = 0; i < m; ++i) ++text[s2[i] - 'a'];

        int start = 0, end = m - 1;

        while (true) {
            if (text == pattern) return true;
            --text[s2[start++] - 'a'];
            ++end;
            if (end >= n) break;
            ++text[s2[end] - 'a'];
        }

        return false;
    }
};