6347Number of vowel string within the scope of statistics

topic

Thought：

Pay attention to pre -processing and prefixing
Prefix and an algorithm，Used to find the prefix and the array。The prefix and definition of the array are defined as the harmony of the prefix element in a certain position of the array。in other words，The prefix and the elements of each position of an array are added to the previous element。

This code uses prefix and to optimize the query process。It pre -processed whether the first letter of each word is a meta sound，Then save these results in a list。Then，It uses prefix and calculate each query result。

Specifically，For each query (i, j)，It will be statistics from words[i] arrive words[j] Conditional conditions（The first letter is a Yuan Yin）Number of words。This can be used by using counts[j+1] - counts[i] To be done。This is because counts[j+1] Contain words[0] arrive words[j] Conditional conditionsNumber of words，and counts[i] Contain words[0] arrive words[i-1] Conditional conditionsNumber of words。therefore，counts[j+1] - counts[i] That words[i] arrive words[j] Conditional conditionsNumber of words。

In the code，counts Arrays use prefix and pre -processing，therefore可以在 O(1) Calculate the results of each query within time。This makes the total running time of the code from coming from O(n^2) Fall to O(n)

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

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        yuanyin = set('aeiou')
        # Traversing each word，Determine whether its first letter is a metaphysical sound
        # Save the results in words_first_last List
        words_first_last = [(word[0] in yuanyin, word[-1] in yuanyin) for word in words]
        # Create counts List，Used to store prefixes and
        counts = [0] * (len(words) + 1)
        # Traversing each word，Calculate prefix and
        for i in range(len(words)):
            counts[i + 1] = counts[i] + int(words_first_last[i][0] and words_first_last[i][1])
        # Traversing each query，Calculate the result of the query
        ans = [counts[j + 1] - counts[i] for i, j in queries]
        # Return result
        return ans