[Leet] - 438. Find All Anagrams in a String [Hash table, Sliding Window] - c++

mopevxw·2022년 2월 3일
0

LeetCode

목록 보기
14/21

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

C++풀이

1. 알파벳을 hash table 구조 적용위해 vector res(26)선언
2. for(auto c : p)res[c-'a']++ => 기준 p를 a~z까지 갯수를 res 배열에 저장
3. s 배열 한칸 씩 진행하면서 cur[s[i]-'a']++ 저장해 가면서 p보다 큰 index에 대해 cur[s[i-ps]-'a']-- 최신화

class Solution {
public:
  vector<int> findAnagrams(string s, string p) {
      vector<int> res(26), cur(26), ans;
      
      for(auto c : p)res[c-'a']++;
      int ps=p.size();
      
      for(int i=0;i<s.size();i++){
          cur[s[i]-'a']++;
          if(i>=ps) cur[s[i-ps]-'a']--;
          if (res==cur) ans.push_back(i-ps+1);
          
      }
      return ans;
  }
};

0개의 댓글