今日题目

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

解题思路

由于每次查询都需要计算某个区间的总和，而任意区间的求和结果对所有查询而言是固定不变的，因此可以使用前缀和来优化。

解题方法

在一次遍历中，我们可以判断 $words[i]$ 是否为元音字符串。基于此，我们可以构建前缀和数组，用于计算索引 1 到索引 i 之间的元音字符串数量。 因此，当需要计算索引 l 到索引 r 之间的元音字符串数量时，只需用 $num(1\space to\space r) - num(1\space to\space l-1)$ 即可得到结果。

小技巧

在 Python 中，$list[-1]$ 表示列表的最后一个元素。因此，我们可以在前缀和数组末尾额外追加一个 [0]，以避免索引越界的问题。

复杂度分析

  • 时间复杂度：$O(k\times N + Q)$，其中 k 为元音字母的数量，N 为 words 的长度，Q 为 queries 的长度。

  • 空间复杂度：$O(N)$，因为我们额外存储了一个新列表。

代码

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