public class Solution
{int nextindex = ;public IList<int> FindAnagrams(string s, string p)
{
List<int> list = new List<int>();
if (s == null || s.Length == || p == null || p.Length == ) return list;
int[] hash = new int[]; //character hash
//record each character in p to hash
foreach (char c in p)
{
hash[c]++;
}
//two points, initialize count to p's length
int left = , right = , count = p.Length;
while (right < s.Length)
{
//move right everytime, if the character exists in p's hash, decrease the count
//current hash value >= 1 means the character is existing in p
if (hash[s[right++]]-- >= ) count--; //when the count is down to 0, means we found the right anagram
//then add window's left to result list
if (count == ) list.Add(left); //if we find the window's size equals to p, then we have to move left (narrow the window) to find the new match window
//++ to reset the hash because we kicked out the left
//only increase the count if the character is in p
//the count >= 0 indicate it was original in the hash, cuz it won't go below 0
if (right - left == p.Length && hash[s[left++]]++ >= ) count++;
}
return list;
}
}
https://leetcode.com/problems/find-all-anagrams-in-a-string/#/description
上面的是别人在讨论区的实现。
下面是我自己的实现，使用非递归方法，性能更好：
public class Solution
{
public IList<int> FindAnagrams(string s, string p)
{
var list = new List<int>();
var dicp = new Dictionary<char, int>();
foreach (var c in p)
{
if (dicp.ContainsKey(c))
{
dicp[c]++;
}
else
{
dicp.Add(c, );
}
}
var dictemp = new Dictionary<char, int>(dicp);
var counttemp = p.Length;
var beginindex = ;
for (var i = ; i < s.Length; i++)
{
var c = s[i];
if (dictemp.ContainsKey(c))
{
if (dictemp[c] > )
{
dictemp[c]--;
counttemp--;
if (counttemp == )
{
list.Add(beginindex); //restore status
dictemp[s[beginindex]]++;
beginindex = beginindex + ;
counttemp++;
}
}
else
{
if (s[beginindex] == c)
{
beginindex = beginindex + ;
}
else
{
beginindex = i;
dictemp = new Dictionary<char, int>(dicp);
dictemp[c]--;
counttemp = p.Length - ;
}
}
}
else
{
beginindex = i + ;
dictemp = new Dictionary<char, int>(dicp);
counttemp = p.Length;
}
}
return list;
}
}