# 2559. Count Vowel Strings in Ranges

• Time: $O(|\texttt{words}| + q)$
• Space: $O(|\texttt{words}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: vector vowelStrings(vector& words, vector>& queries) { vector ans; // prefix[i] := # of first i words that start and end with a vowel vector prefix(words.size() + 1); for (int i = 0; i < words.size(); ++i) prefix[i + 1] += prefix[i] + startsAndEndsWithVowel(words[i]); for (const vector& query : queries) { const int l = query[0]; const int r = query[1]; ans.push_back(prefix[r + 1] - prefix[l]); } return ans; } private: bool startsAndEndsWithVowel(const string& word) { return isVowel(word.front()) && isVowel(word.back()); } bool isVowel(char c) { static constexpr string_view kVowels = "aeiou"; return kVowels.find(c) != string_view::npos; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public int[] vowelStrings(String[] words, int[][] queries) { int[] ans = new int[queries.length]; // prefix[i] := # of first i words that start and end with a vowel int[] prefix = new int[words.length + 1]; for (int i = 0; i < words.length; ++i) prefix[i + 1] += prefix[i] + (startsAndEndsWithVowel(words[i]) ? 1 : 0); for (int i = 0; i < queries.length; ++i) { final int l = queries[i][0]; final int r = queries[i][1]; ans[i] = prefix[r + 1] - prefix[l]; } return ans; } private boolean startsAndEndsWithVowel(final String word) { return isVowel(word.charAt(0)) && isVowel(word.charAt(word.length() - 1)); } private boolean isVowel(char c) { return "aeiou".indexOf(c) != -1; } } 
  1 2 3 4 5 6 7 8 9 10 11 class Solution: def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]: kVowels = 'aeiou' # prefix[i] := # of first i words that start and end with a vowel prefix = [0] * (len(words) + 1) for i, word in enumerate(words): prefix[i + 1] += prefix[i] + (word[0] in kVowels and word[-1] in kVowels) return [prefix[r + 1] - prefix[l] for l, r in queries]