Count Vowel Strings in Ranges(Array,String,Prefix Sum)

https://leetcode.com/problems/count-vowel-strings-in-ranges/description/?envType=daily-question&envId=2025-01-02

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'.

 

Example 1:

Input: words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]

Output: [2,3,0]

Explanation: The strings starting and ending with a vowel are "aba", "ece", "aa" and "e".

The answer to the query [0,2] is 2 (strings "aba" and "ece").

to query [1,4] is 3 (strings "ece", "aa", "e").

to query [1,1] is 0.

We return [2,3,0].

Example 2:

Input: words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]

Output: [3,2,1]

Explanation: Every string satisfies the conditions, so we return [3,2,1].

 

Constraints:

1 <= words.length <= 105

1 <= words[i].length <= 40

words[i] consists only of lowercase English letters.

sum(words[i].length) <= 3 * 105

1 <= queries.length <= 105

0 <= li <= ri < words.length

---

 

웬지 문제가 좀 쉽다 했다 ㅋㅋ

 

1. Python

 

바로 Time - limit CUT.... -_-

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        vowel = ['a','e','i','o','u']
        ans = []
        for s,e in queries :
            # count the number of target
            cnt = 0
            for i in range(s,e+1):
                if words[i][0] in vowel and words[i][-1] in vowel:
                    cnt +=1
            ans += [cnt]
        return ans

 

아 옘~병

 

for문 겹치는 걸 분리했는데도 Time Limit이 걸린다 -_-

 

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        vowel = {'a','e','i','o','u'}
        ans = []
        for i in range(len(words)):
            if words[i][0] in vowel and words[i][-1] in vowel :
                words[i] = 1
            else : words[i] = 0
        for s,e in queries :
            ans.append(sum(words[s:e+1]))
        return ans

 

아.. 이 코드 가지곤 이래 저래 굴려봐도 해결이 안 되는데,

 

문제 주제에 있던 Prefix - Sum ( 구간합 )을 이용해야 한다.

 

구간합 설명은 아래 링크 글 참고

https://developer-cat.tistory.com/18

[알고리즘] - 구간 합 (Prefix sum)

 

즉, Space를 좀 사용하므로써 Speed를 살리는 행위다.

 

요렇게 풀이가 가능!

 

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        vowel = {'a','e','i','o','u'}
        # O(N)
        for i in range(len(words)):
            if words[i][0] in vowel and words[i][-1] in vowel :
                words[i] = 1
            else : words[i] = 0
        # Prefix processing O(N)
        prefix_sum = [words[0]]*len(words)
        for j in range(len(words)-1):
            prefix_sum[j+1] = prefix_sum[j]+words[j+1]
        # Answering O(N)
        ans = []
        for s,e in queries :
            if s==0 : ans.append(prefix_sum[e])
            else: ans.append(prefix_sum[e]-prefix_sum[s-1])
        return ans

 

 

2. C, C++도 유사하게 풀 수 있을 거 같다.

 

C는 좀 추잡하다.. String 에서 char 찾는 거 strchr 사용!

 

 

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* vowelStrings(char** words, int wordsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    char vowel[] = {"aeiou"};
    int prefix[wordsSize];

    int* words_num = (int*)malloc(wordsSize*sizeof(int));
    for(int i=0;i<wordsSize;i++){
        int n = strlen(words[i]);
        if(strchr(vowel,words[i][0]) && strchr(vowel,words[i][n-1])) words_num[i] = 1;
        else words_num[i] = 0;
    }

    prefix[0] = words_num[0];
    for(int j=1;j<wordsSize;j++){
        prefix[j] = prefix[j-1] + words_num[j];
    }

    int* ans = (int*)malloc(queriesSize * sizeof(int));
    for(int p=0;p<queriesSize;p++){
        int s = queries[p][0];
        int e = queries[p][1];
        if(s==0) ans[p] = prefix[e];
        else ans[p] = prefix[e] - prefix[s-1];
    }
    *returnSize = queriesSize;
    free(words_num);
    return ans;
}

 

C++는

Vector 선언해줄때 push_back을 쓰려면 vec(3) 이렇게 크기를 정하면 안 되고, 생짜 vec에서 push_back을 3번해야 원하는 만큼(3 회) element가 추가된 vector를 얻을 수 있다.

 

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        int n = words.size();
        vector<char> vowel = {'a','e','i','o','u'};
        vector<int> vec;
        for(const string x : words){
            int len = x.size();
            if(find(vowel.begin(),vowel.end(),x[0])!=vowel.end() && find(vowel.begin(),vowel.end(),x[len-1])!=vowel.end()) vec.push_back(1);
            else vec.push_back(0);
        }

        vector<int> prefix(n);
        prefix[0] = vec[0];
        for(int i=1;i<n;i++) prefix[i] = prefix[i-1]+vec[i];
        
        int m = queries.size();
        vector<int> ans;

        for(auto pair : queries){
            int s = pair[0];
            int e = pair[1];
            if(s==0) ans.push_back(prefix[e]);
            else ans.push_back(prefix[e]-prefix[s-1]);
        }
        return ans;
    }
};