Given two strings
s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.In other words, return
true if one of s1‘s permutations is the substring of s2.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
Constraints:
1 <= s1.length, s2.length <= 10<sup>4</sup>
s1 and s2 consist of lowercase English letters.题目大意：
求字符串s2中是否含s1的anagram
解题思路：
类似于LeetCode 438 Find All Anagrams in a String, 唯一区别是substr_win == char_to_count_p时返回而不是加入到res
解题步骤：
N/A
注意事项：
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13def checkInclusion(self, s1: str, s2: str) -> bool:
char_to_count_p = collections.Counter(s1)
substr_win = collections.defaultdict(int)
for i, char in enumerate(s2):
substr_win[s2[i]] += 1
# window: [i - len(p) + 1, i]
if i >= len(s1):
substr_win[s2[i - len(s1)]] -= 1
if substr_win[s2[i - len(s1)]] == 0:
substr_win.pop(s2[i - len(s1)])
if substr_win == char_to_count_p:
return True
return False
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
