567. Permutation in String

本文主要是介绍567. Permutation in String，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 长度为1if (map2 == map1 && i != n)res.push_back(i);return res;
}