567. 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:
The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].
先祭出来自己的低效率算法，low比算法，虽然过了，但是自己都很不满意。
bool checkInclusion1(string s1, string s2) {
if (s1 == "" && s2 == "")return true;
if (s1 == "" || s2 == "" || s1.size() > s2.size())return false;
unordered_map<char, int> temp;
for (auto x : s1)temp[x]++;
for (int i = 0; i < s2.size(); i++){
if (s1.find(s2[i]) != string::npos){
unordered_map<char, int> tt = temp;
if (s2.size() - i < s1.size())return false;
string str = s2.substr(i, s1.size());
for (int ii = 0; ii < s1.size(); ii++) --tt[str[ii]];
bool flag = false;
for (auto x : tt){
if (x.second < 0){
flag = true;
break;
}
}
if (!flag)return true;
}
}
return false;
}
算法时间复杂度为O(m*n)，空间复杂度为O(2*m)
参考算法
bool checkInclusion(string s1, string s2) {
if (s1.size() > s2.size())return false;
int m = s1.size(), n = s2.size();
vector<int> map1(26), map2(26);
for (int i = 0; i < m; i++){
map1[s1[i] - 'a']++;
map2[s2[i] - 'a']++;
}
if (map1 == map2)return true;
for (int i = 0; i + m < n; i++){
map2[s2[i] - 'a']--;
map2[s2[i + m] - 'a']++;
if (map2 == map1)return true;
}
return false;
}
用了流动窗口的思想，虽然要求是全排列，但只要保证两个字串的每个元素的个数是相同就可以了。
时间复杂度为O(n)，空间复杂度为O(n)；
切记，一定要心情好的时候刷题，不然总是一头雾水，虽然做出来了，但是，效率低的自己都觉得不好意思。。。
这个题与上一个题目很类似
438. Find All Anagrams in a String
Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input:
s: “cbaebabacd” p: “abc”
Output:
[0, 6]
Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Example 2:
Input:
s: “abab” p: “ab”
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.
vector<int> findAnagrams(string s, string p) {
vector<int> res;
vector<int> map1(26), map2(26);
int m = p.size(), n = s.size();
for (int i = 0; i < m; i++){
map1[p[i] - 'a']++;
map2[s[i] - 'a']++;
}
int i = 0;
for (; i + m < n; i++){
if (map2 == map1)res.push_back(i);
map2[s[i] - 'a']--;
map2[s[i + m] - 'a']++;
}
//这里的 i != n 主要是针对 p 长度为1
if (map2 == map1 && i != n)res.push_back(i);
return res;
}
