Skip to content

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
31
class Solution {
 public:
  vector<int> vowelStrings(vector<string>& words,
                           vector<vector<int>>& queries) {
    vector<int> ans;
    // prefix[i] := the number of the first i words that start with and end in a
    // vowel
    vector<int> prefix(words.size() + 1);

    for (int i = 0; i < words.size(); ++i)
      prefix[i + 1] += prefix[i] + startsAndEndsWithVowel(words[i]);

    for (const vector<int>& 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] := the number of the first i words that start with and end in 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] := the number of the first i words that start with and end in 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]