【leetcode】438. Find All Anagrams in a String（Python & C++）

---

438. Find All Anagrams in a String

题目链接

438.1 题目描述：

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”.

438.2 解题思路：

思路一：首先利用vector b记录string p每个字符的个数。然后依次遍历string s，在每次遍历中，用vector temp内循环遍历s当前坐标i到p.length()个长度的每个字符的个数，然后判断b是否与temp相等即可，若相等，则将当前坐标i放进要返回的vector中。继续外循环。

思路二：同思路一一样，不过进行优化，利用滑动窗口，在第一次用vector a记录p的字符的个数时，也同时用vector b记录s中前p.length()个字符的个数，判断a==b，若成立，将0放进要返回的vector。然后开始从i=1，i小于s.length()滑动窗口，每次滑动一个字符，将s中i-1处对应的字符在b中的个数减1，而s中i-1+p.length()处对应的字符在b中的个数加1，这样不需要思路一种每次遍历p.length()个字符，只需要改动两个位置即可。然后判断a==b，若成立，将i放进要返回的vector。继续循环即可。

438.3 C++代码：

1、思路一代码（506ms）：

class Solution106 { public: vector<int> findAnagrams(string s, string p) { vector<int>a; if (s.length() < p.length()) return a; vector<int>b(27,0); for (int i = 0; i < p.length(); i++) b[p[i]-'a']++; for (int i = 0; i < s.length();i++) { vector<int>temp(27, 0); if (i + p.length() > s.length()) break; for (int j = i; j < i + p.length(); j++) temp[s[j]-'a']++; if (b == temp) a.push_back(i); } return a; } };

2、思路二代码（33ms）：

class Solution106_1 { public: vector<int> findAnagrams(string s, string p) { vector<int>a; if (s.length() < p.length()) return a; vector<int>sc(27, 0); vector<int>pc(27, 0); for (int j = 0; j < p.length();j++) { pc[p[j] - 'a']++; sc[s[j] - 'a']++; } if (pc == sc) a.push_back(0); for (int i = 1; i < s.length();i++) { if (i+p.length()>s.length()) break; sc[s[i-1] - 'a']--; sc[s[i+p.length()-1] - 'a']++; if (pc == sc) a.push_back(i); } return a; } };

438.4 Python代码：

1、思路二代码（172ms）：

class Solution(object): def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """ a=[0]*26 b=[0]*26 res=[] if len(s)<len(p): return res for i in range(0,len(p)): a[ord(p[i])-ord('a')]+=1 b[ord(s[i])-ord('a')]+=1 if a==b: res.append(0) for j in range(1,len(s)): if j+len(p)>len(s): break b[ord(s[j-1])-ord('a')]-=1 b[ord(s[j+len(p)-1])-ord('a')]+=1 if a==b: res.append(j) return res

---