[Sliding Window][Medium] 438. Find All Anagrams in a String

https://leetcode.com/problems/find-all-anagrams-in-a-string/description

 

Q. 두개의 string s와 p가 주어질 때, p의 anagram이 되는 s의 substring을 찾고, 그 시작 index 목록을 반환하라. 

 

 

Solution

 p에 대해 frequency buffer를 만들고 해당 버퍼를 모두 가진 구간이 있는지 확인한다. 

비교적 간단한 문제. 

 

코드.

public IList<int> FindAnagrams(string s, string p) 
{
    IList<int> ret = new List<int>();
    Dictionary<char, int> dictFreq = new Dictionary<char, int>();
    for(int q = 0; q < p.Length; ++q)
    {
        if(dictFreq.ContainsKey(p[q]))
            ++dictFreq[p[q]];
        else 
            dictFreq.Add(p[q], 1);
    }

    int left = 0;
    int right = 0;
    for(; right < s.Length; ++right) 
    {
        char cur = s[right];
        if(dictFreq.ContainsKey(cur))
            --dictFreq[cur];

        if(right-left+1 == p.Length)
        {
            bool hit = true;
            foreach(var keys in dictFreq.Keys) 
            {
                if(dictFreq[keys] != 0)
                {
                    hit = false;
                    break;
                }
            }
            if(hit) ret.Add(left);

            char leftOne = s[left++];
            if(dictFreq.ContainsKey(leftOne))
                ++dictFreq[leftOne];
        }
    }
    return ret;
}

 

 

적절한 결과를 얻었다.