[leetcode 438] 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]

 

문제: s 내에서 p에 해당하는 문자열(순서에 상관없이)의 시작점을 찾기

 

풀이

- map과 슬라이딩 윈도우가 필요

- p의 길이만큼 s의 구간을 정해서 p와 동일한지 체크한다. 이 때 순서에 상관없이 같으면 되므로 알파벳 개수 일치여부만 체크한다.

- map은 직접 라이브러리를 사용해도 되고 배열을 선언해서 사용해도 된다.

 

class Solution {
public:
   
    vector<int> findAnagrams(string s, string p) {
        vector<int> answer;
        
        int sLen = s.length();
        int pLen = p.length();
        
        if(sLen < pLen){
            return answer;
        }
        
        map<char, int> m1, m2;
        
        for(int i=0; i<pLen; i++){
            m1[s[i]]++;
            m2[p[i]]++;
        }
        
        int i;
        for(i=pLen; i<sLen; i++){
            if(m1 == m2){
                answer.push_back(i-pLen);
            }
            
            m1[s[i]]++;
            m1[s[i-pLen]]--;
            
            if( m1[s[i-pLen]] == 0){
                m1.erase(s[i-pLen]);
            }
        }
        
        if(m1 == m2){
            answer.push_back(i-pLen);
        }
        
        return answer;
    }
};

 

시간을 더 줄인 코드

class Solution {
public:
   
    vector<int> findAnagrams(string s, string p) {
        vector<int> answer;
        
        int sLen = s.length();
        int pLen = p.length();
        
        if(sLen < pLen){
            return answer;
        }
        
        vector<int> v1(26,0);
        vector<int> v2(26,0);
        
        for(int i=0; i<pLen; i++){
            v1[s[i]-'a']++;
            v2[p[i]-'a']++;
        }
        
        if(v1 == v2){
            answer.push_back(0);
        }
        
        int i;
        for(i=pLen; i<sLen; i++){
           
            v1[s[i]-'a']++;
            v1[s[i-pLen] -'a']--;
            
            if(v1 ==v2){
                answer.push_back(i-pLen+1);
            }
        }
    
        return answer;
    }
};