438. Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

anagram 이란 글자의 배치순서만 다른것이다 abc 의 anagram 은 acb,bac,bca,cab,cba 등이 있다
s 스트링에서 p의 anagram 찾고 첫번째 인덱스를 반환하는 문제이다

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

c++ 로 8월에 이미 풀었던 문제임에도 불구하고 푸는데 3시간이나 걸렸다...
java로 풀어보았다

해시맵과 슬라이딩윈도우(알고리즘?)을 사용하였다

public List<Integer> findAnagrams(String s, String p) 
{
        List<Integer> ret = new ArrayList<Integer>();

        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
      
        for(int i = 0; i < p.length(); ++i)
        {
            if(map.get(p.charAt(i)) == null)
                map.put(p.charAt(i), 1);
            else
                map.put(p.charAt(i), map.get(p.charAt(i)) + 1);
        }

        int left = 0;
        int right = 0;
 
        while(right < s.length())
        {
            if(map.get(s.charAt(right)) != null)
            {
                map.put(s.charAt(right), map.get(s.charAt(right)) - 1);
            }

            right++;

            if((right - left) > p.length())
            {
                if(map.get(s.charAt(left)) != null)
                {
                    map.put(s.charAt(left), map.get(s.charAt(left)) + 1);
                }
                left++;
            }

            boolean isAllZero = true;
            for (Map.Entry<Character, Integer> set : map.entrySet()) 
            {
                if( 0 != set.getValue())
                {
                    isAllZero = false;
                    break;
                }                
            }
                
            if(isAllZero==true)
            {
                ret.add(left);
            }
        }

        return ret;
    }

코드가 너무 길다.. 비효율적인 부분을 줄이는게 항상 어렵다.. 예를들어 해시맵에서 글자마다 숫자를 카운트 하고 매번 전부 0인지 확인하는 것보다 더 좋은 방법이 있지않을까 생각해본다.

예전에 c++로 풀었던 기록이 남아있네! 릿코드에서 submit 하면 코드 기록을 저장하는것 같다

vector<int> findAnagrams(string s, string p) 
  {

        vector<int> ret;
        
        map<char,int> hashmap;
        
        map<char,int>::iterator iter;

        for(int i = 0; i < p.length(); ++i)
        {
            iter = hashmap.find(p[i]);
            if(iter != hashmap.end())
                iter->second += 1;
            else
                hashmap.insert(make_pair(p[i], 1));
        }
        
        int begin = 0;
        int end = begin + p.length() -1;

        int hashsize = hashmap.size();
        
         for(int i = 0; i < p.length(); ++i)
         {         
             iter = hashmap.find(s[i]);
             if(iter != hashmap.end())
             {
                 iter->second -= 1;
                 if(iter->second ==0 )
                    hashsize--; 
             }
                 
         
             if(0 == hashsize)
                 ret.push_back(begin);
         }
        
        ++begin;
        ++end;

        
        while(end < s.length())
        {   
            iter = hashmap.find(s[begin-1]);
            if(iter != hashmap.end())
            {            
                iter->second += 1;
                if(iter->second == 1)
                    hashsize++;
            }
           
            iter = hashmap.find(s[end]);
            if(iter != hashmap.end())
            {
                iter->second -= 1;
                if(iter->second == 0)
                    hashsize--;
            }
        
            
            if(0 == hashsize)
                ret.push_back(begin);
            
            ++begin;
            ++end;
        }         
            
        

     
        return ret;
                   
    }

차이점은 hashsize 변수를 추가하고 각각 글자의 개수가 0이면 -하고 글자가 1되면 + 카운트를 하는것이다. 그러면 전체 순회하면서 전부 0인지 체크하는 코드가 필요없게 된다

public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<Integer>();

        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
      
        int hashcount = 0;
        for(int i = 0; i < p.length(); ++i)
        {
            if(map.get(p.charAt(i)) == null)
            {
                map.put(p.charAt(i), 1);
                hashcount++;
            }             
            else
            {
                map.put(p.charAt(i), map.get(p.charAt(i)) + 1);
            }
                
        }

        int left = 0;
        int right = 0;

        while(right < s.length())
        {
            if(map.get(s.charAt(right)) != null)
            {
                map.put(s.charAt(right), map.get(s.charAt(right)) - 1);
                if(map.get(s.charAt(right)) == 0)
                    hashcount--;
            }

            if((right - left) > p.length()-1)
            {
                if(map.get(s.charAt(left)) != null)
                {
                    map.put(s.charAt(left), map.get(s.charAt(left)) + 1);
                    if(map.get(s.charAt(left)) == 1)
                        hashcount++;
                }
                left++;
            }

            right++;

            if(hashcount == 0)
            {
                ret.add(left);
            }
        }

        return ret;
    }

코드를 개선했지만 속도는 그닥 차이가 나지 않는다