[LeetCode] 1160. Find Words That Can Be Formed by Characters

https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/description/

Find Words That Can Be Formed by Characters - LeetCode

leetcode - Find Words That Can Be Formed by Characters

문제 유형 : 문자열 처리 / 해싱

문제 난이도 : Easy

 

문제

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

 

당신은 문자열 배열 words와 문자열 chars를 받습니다.

어떤 문자열이 chars문자열에 있는 문자들로 구성될 수 있을 때, 좋은 문자열이라고 할 수 있습니다.

words배열의 좋은 문자열들의 길이의 합을 반환하시오.

 

 

풀이

chars배열을 한 번 순회하면서 각 알파벳들이 몇 개 있는지 저장해둔다.

 

words배열의 각 문자들을 탐색하면서, 그 요소를 만들 때 필요한 문자들을 계산한다.

요구되는 문자들이 chars로 만들 수 없어지면(특정 알파벳의 개수가 chars의 그 알파벳 개수보다 많으면) 누적 값에 더하지 않는다.

만들 수 있다고 판단되면, words배열의 요소를 누적 값에 더한다.

이 누적 값을 반환해준다.

 

알파벳들별로 개수 저장은 배열이나 해시 테이블 자료구조를 이용해주면 된다.

 

 

코드

C++

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        unordered_map<char, int> charTable;
        int answer = 0;

        for(const auto &ch : chars) 
            charTable[ch]++;
        
        for(const auto &word : words) {
            unordered_map<char, int> tempTable;
            bool flag = true;
            for(const auto &ch : word) {
                tempTable[ch]++;
                if(tempTable[ch] > charTable[ch]) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                answer += word.size();
            }
        }

        return answer;
    }
};