[LeetCode] 2559. Count Vowel Strings in Ranges

https://leetcode.com/problems/count-vowel-strings-in-ranges/description/

leetcode - Count Vowel Strings in Ranges

문제 유형: 문자열 처리, 부분합

문제 난이도: Medium

 

문제

You are given a 0-indexed array of strings words and a 2D array of integers queries.

Each query queries[i] = [li, ri] asks us to find the number of strings present in the range li to ri (both inclusive) of words that start and end with a vowel.

Return an array ans of size queries.length, where ans[i] is the answer to the ith query.

Note that the vowel letters are 'a', 'e', 'i', 'o', and 'u'.

 

문자열 2D배열 words와 정수 2D배열 queries가 주어진다.

queries[i] = [li, ri]는 [li, ri]구간의 words에서 모음인 words의 요소의 개수이다.

queries의 응답을 담은 ans배열을 반환하시오.

 

풀이

미리 prefixSum에 [0:i]에 대한 prefixSum을 프리컴퓨트 한다.

각 word를 읽으면서 모음으로 시작하고 끝나는 단어인지 확인하고 맞다면 prefixSum[i]에 1을 더한다. i >=1인경우, prefisSum[i-1]도 누적한다.

그 뒤, 쿼리에 맞게 부분합을 이용해서 응답하면 된다. [l, r]로 온 쿼리에 대해 prefixSum[r] - prefixSum[l-1]을 빼면 된다.

l=0인경우, 안빼면 된다.

 

코드

C++

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        unordered_map<char, bool> isvowel = {
            {'a', true},
            {'e', true},
            {'i', true},
            {'o', true},
            {'u', true}
        };
        int n = words.size();
        vector<int> prefixSum(n, 0);

        for(int i = 0; i < n; ++i) {
            if(isvowel[words[i][0]] && isvowel[words[i][words[i].size()-1]]) prefixSum[i]++;
            if(i >= 1) prefixSum[i] += prefixSum[i-1];
        }

        vector<int> ans;
        for(const auto &query : queries) {
            int l = query[0];
            int r = query[1];
            if(l == 0) ans.push_back(prefixSum[r]);
            else ans.push_back(prefixSum[r] - prefixSum[l-1]);
        }
        return ans;
    }
};