LeetCode 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".

---

给定两个字符串s和p，要从s中找出所有和p是变位词的子串的起始位置。 判断两个字符串是否为变位词，可以用Hash的方法，在LeetCode Group Anagrams中已经介绍过了。 本题的思路也很简单，遍历s，每次从左端删掉一个字符，加入右端的一个字符，判断s和p的Hash表是否相等，相等就说明是一个变位词。 代码如下： [cpp] class Solution { public: vector<int> findAnagrams(string s, string p) { int slen = s.size(), plen = p.size(); if (slen < plen)return vector<int>(); vector<int> ans; vector<int> hash1(26, 0), hash2(26, 0); for (int i = 0; i < plen; ++i) { ++hash1[s[i] – ‘a’]; ++hash2[p[i] – ‘a’]; } if (hash1 == hash2)ans.push_back(0); for (int i = plen; i < slen; ++i) { –hash1[s[i – plen] – ‘a’]; ++hash1[s[i] – ‘a’]; if (hash1 == hash2)ans.push_back(i – plen + 1); } return ans; } }; [/cpp] 本代码提交AC，用时33MS。]]>