[LeetCode] 1002. Find Common Characters

https://leetcode.com/problems/find-common-characters/description/

 

leetcode - Find Common Characters

문제 유형 : 문자열 처리, 구현

문제 난이도 : Easy

 

문제

Given a string array words, return an array of all characters that show up in all strings within the words (including duplicates). You may return the answer in any order.

 

문자열 배열 words가 주어진다. words의 모든 문자들에서 겹치는 문자들을 찾아 반환하시오. 어떤 순서든 상관없습니다.

 

풀이

freq(26,1e9) 배열을 만들어서 알파벳의 빈도를 추적한다.

각 문자별로 subfreq(26, 0)을 만들어서 각 단어별로 빈도를 센다.

freq = min(subfreq, freq)로 최소값을 업데이트한다. 이것이 각 문자별로 중복된 개수이다.

 

최종적으로 있는 freq에 따라서 정답 배열에 추가해주면 된다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<string> commonChars(vector<string>& words) {
        vector<int> freq(26, 1e9);
        
        for(auto &word : words) {
            vector<int> subfreq(26, 0);

            for(char &ch : word) {
                subfreq[ch - 'a']++;
            }

            for(int i = 0; i < 26; i++) {
                freq[i] = min(freq[i], subfreq[i]);
            }
        }

        vector<string> ans;
        for(int i = 0; i < 26; i++) {
            for(int j = 0; j < freq[i]; j++) {
                ans.push_back(string(1, 'a'+i));
            }
        }

        return ans;
    }
};