Count Vowel Strings in Ranges

Leetcode Problem:

• Count Vowel Strings in Ranges

Summary

• Given a list of strings and queries, find the number of strings that start and end with a vowel.

Approach

• Use a prefix sum array to store the count of strings that start and end with a vowel
• Then, for each query, subtract the count of strings that start at the query's left index from the count of strings that end at the query's right index.

Complexity

• O(n + m * q) where n is the number of strings, m is the maximum length of a string, and q is the number of queries.

Explanation

• The prefix sum array is initialized with all zeros
• Then, for each string, if the first and last characters are both vowels, increment the count at that index
• Finally, for each query, subtract the count at the left index from the count at the right index to get the answer.

Solution Code:

class Solution {
public:
    int pSum[100002];

    bool isVowel(char c){
        if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'){
            return true;
        }
        return false;
    }
    vector vowelStrings(vector& words, vector>& queries) {
        for(int i = 0 ; i < words.size(); i++){
            pSum[i+1] = pSum[i];
            string s = words[i];
            if(isVowel(s[0]) && isVowel(s[s.size() - 1])){
                pSum[i+1]++;
            }
        }
        vector ans;
        for(int i = 0 ; i < queries.size(); i++){
            ans.push_back(pSum[queries[i][1]+1] - pSum[queries[i][0]]);
        }
        return ans;
    }
};