# [LeetCode] 567. Permutation in String 字符串中的全排列

2021年09月15日 阅读数：1

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:html

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

Example 2:java

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

Note:python

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

Java:url

```public class Solution {
public boolean checkInclusion(String s1, String s2) {
int len1 = s1.length(), len2 = s2.length();
if (len1 > len2) return false;

int[] count = new int[26];
for (int i = 0; i < len1; i++) {
count[s1.charAt(i) - 'a']++;
count[s2.charAt(i) - 'a']--;
}
if (allZero(count)) return true;

for (int i = len1; i < len2; i++) {
count[s2.charAt(i) - 'a']--;
count[s2.charAt(i - len1) - 'a']++;
if (allZero(count)) return true;
}

return false;
}

private boolean allZero(int[] count) {
for (int i = 0; i < 26; i++) {
if (count[i] != 0) return false;
}
return true;
}
}
```

Java:rest

```public class Solution {
public boolean checkInclusion(String s1, String s2) {
int[] map = new int[26];
int sum = s1.length();
// construct frequency map
for(int i = 0; i< s1.length(); i++){
map[s1.charAt(i) - 'a']++;
}
for(int r = 0, l = 0; r < s2.length(); r++){
char c = s2.charAt(r);
if(map[c - 'a'] > 0){
map[c - 'a']--;
sum--;
//check for permutation match.
if(sum == 0) return true;
}else{
// if there is enough number for char c or c is never seen before.
// we move left pointer next to the position where we first saw char c
// or to the r+1(we never see char c before),
//and during this process we restore the map.
while(l<= r && s2.charAt(l) != s2.charAt(r)){
map[s2.charAt(l) - 'a'] ++;
l++;
sum++;
}
l++;
}
}
return false;
}
}　　```

Python:htm

```def checkInclusion(self, s1, s2):
A = [ord(x) - ord('a') for x in s1]
B = [ord(x) - ord('a') for x in s2]

target = [0] * 26
for x in A:
target[x] += 1

window = [0] * 26
for i, x in enumerate(B):
window[x] += 1
if i >= len(A):
window[B[i - len(A)]] -= 1
if window == target:
return True
return False
```

Python:blog

```class Solution(object):
def checkInclusion(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
counts = collections.Counter(s1)
l = len(s1)
for i in xrange(len(s2)):
if counts[s2[i]] > 0:
l -= 1
counts[s2[i]] -= 1
if l == 0:
return True
start = i + 1 - len(s1)
if start >= 0:
counts[s2[start]] += 1
if counts[s2[start]] > 0:
l += 1
return False　　```

C++:

```class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n1 = s1.size(), n2 = s2.size();
vector<int> m1(128), m2(128);
for (int i = 0; i < n1; ++i) {
++m1[s1[i]]; ++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;
}
};　　```

C++:

```class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n1 = s1.size(), n2 = s2.size(), left = 0;
vector<int> m(128);
for (char c : s1) ++m[c];
for (int right = 0; right < n2; ++right) {
if (--m[s2[right]] < 0) {
while (++m[s2[left++]] != 0) {}
} else if (right - left + 1 == n1) return true;
}
return n1 == 0;
}
};
```

C++:

```class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n1 = s1.size(), n2 = s2.size(), cnt = n1, left = 0;
vector<int> m(128);
for (char c : s1) ++m[c];
for (int right = 0; right < n2; ++right) {
if (m[s2[right]]-- > 0) --cnt;
while (cnt == 0) {
if (right - left + 1 == n1) return true;
if (++m[s2[left++]] > 0) ++cnt;
}
}
return false;
}
};
```

[LeetCode] 438. Find All Anagrams in a String 找出字符串中全部的变位词