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:
- The input strings only contain lower case letters.
- The length of both given strings is in range [1, 10,000].
给2个字符串s1和s2，写一个函数能够返回是否s1的全排列中存在着一个是s2的子字符串。
虽然题目中有全排列，但跟以前的全排列的题目的解法并不一样，如果遍历s1所有全排列的情况，然后检测其是否为s2的子串，非常不高效。 其实并不需要知道s1的全排列情况，只要知道s2中一个长度和s1一样的子字符串所含的字符一样就可以了。和438. Find All Anagrams in a String 类似。
解法：滑动窗口法
Java:
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:
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:
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:
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 找出字符串中所有的变位词