Here is the link.
Second practice - C# - Linear time - Counting sort
Dec. 29, 2020
Introduction
My first practice ran into time out problem since the sorting is applied. I read the problem statement again and then decide to use counting sort with linear time, the problem is solved.
Edge case
I ran into the wrong answer, so that I figured out that extra checking is needed in the function isAnagram.
if(count[item - 'a'] < 1 )
{
return false;
}
20 days break
I just took 20 days break after Dec. 8. It is surprising to learn from my two mistakes I had in my practice.
public class Solution {
public IList<int> FindAnagrams(string s, string p) {
if(s == null || p == null || s.Length == 0 || p.Length == 0 || s.Length < p.Length)
return new List<int>();
var sLength = s.Length;
var pLength = p.Length;
var list = new List<int>();
for(int i = 0; i < sLength && i + pLength <= sLength; i++)
{
var substring = s.Substring(i, pLength);
if(isAnagram(substring, p))
{
list.Add(i);
}
}
return list;
}
private bool isAnagram(string s, string t)
{
var count = new int[26];
foreach(var item in s)
{
count[item - 'a']++;
}
foreach(var item in t)
{
if(count[item - 'a'] < 1 )
{
return false;
}
count[item - 'a']--;
}
return count.Sum() == 0;
}
}
