Today’s problem

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

Intuition

We need to cacluate the sum of a section, while the sum of the any section remains constant for every query. Therefore we can use prefix sum.

Approach

In one iteration, we can identify whether $words[i]$ is the a vowel string or not. In this case, we can apply a prefix sum to calculate the number of vowel strings between index 1 and index i. Therefore, when we want to calculate the number of vowel strings between index l and index r, we can just use $num(1\space to\space r) - num(1\space to\space l-1)$ as our result.

Trick

In python, $list[-1]$ means the final index of the list. Therefore, we can add a [0] at the end of our prefix sum list to avoid null index.

Complexity

• Time complexity: $O(k\times N + Q)$, while k is the number of vowels, N is the length of the words, Q is the length of the queries.

• Space complexity: $O(N)$, because we stored a new list.

Code

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        sumWords = [0] * (len(words) + 1)
        vowels = set(['a','e','i','o','u'])
        for idx, word in enumerate(words):
            sumWords[idx] = sumWords[idx-1]
            if word[0] in vowels and word[-1] in vowels:
                sumWords[idx] += 1

        ans = []
        for x,y in queries:
            ans.append(sumWords[y] - sumWords[x-1])
        
        return ans