2559. 统计范围内的元音字符串数(前缀和) o(n)时间复杂度

给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。

每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内（包含 这两个值）并且以元音开头和结尾的字符串的数目。

返回一个整数数组，其中数组的第 i 个元素对应第 i 个查询的答案。

注意：元音字母是 'a'、'e'、'i'、'o' 和 'u' 。

示例 1：

输入：words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]

输出：[2,3,0]

解释：以元音开头和结尾的字符串是 "aba"、"ece"、"aa" 和 "e" 。

查询 [0,2] 结果为 2（字符串 "aba" 和 "ece"）。

查询 [1,4] 结果为 3（字符串 "ece"、"aa"、"e"）。

查询 [1,1] 结果为 0 。

返回结果 [2,3,0] 。

示例 2：

输入：words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]

输出：[3,2,1]

解释：每个字符串都满足这一条件，所以返回 [3,2,1] 。

提示：

• 1 <= words.length <= 105
• 1 <= words[i].length <= 40
• words[i] 仅由小写英文字母组成
• sum(words[i].length) <= 3 * 105
• 1 <= queries.length <= 105
• 0 <= queries[j][0] <= queries[j][1] < words.length

class Solution(object):
    def vowelStrings(self, words, queries):
        nums = [0] * (len(words))
        for i in range(len(words)):
            # 检查单词是否以元音字母开头和结尾
            if words[i][0] in ['a','e','i','o','u'] and words[i][-1] in ['a','e','i','o','u']:
                nums[i] = 1
        
        # 计算前缀和
        presum = 0
        pre = [0] * (len(words))
        for i in range(len(words)):
            presum += nums[i]
            pre[i] = presum
        
        ans = []
        for i in queries:
            count = 0
            if i[0] == 0:
                count = pre[i[1]]
            else:
                count = pre[i[1]] - pre[i[0] - 1]
            ans.append(count)
        return ans

1. **预处理：**首先，对给定的单词列表进行预处理，对于每个单词，检查其是否以元音字母开头和结尾。如果是，则将对应的 nums 数组的对应位置标记为 1，表示该位置的单词满足条件，否则标记为 0。

2. **前缀和：**然后，使用前缀和技巧来快速计算出满足条件的单词数。创建一个前缀和数组 pre，其中 pre[i] 表示从单词列表的开头到第 i 个单词（包括第 i 个单词）满足条件的单词数的累计和。遍历 nums 数组，并计算累计和，将结果存储在 pre 数组中。

3. **查询处理：**对于每个查询范围 [start, end]，我们可以利用前缀和数组 pre 来计算该范围内满足条件的单词数。如果查询范围的起始位置为 0，则直接取 pre[end] 作为答案；否则，我们可以通过计算 pre[end] - pre[start - 1] 来得到该范围内的满足条件的单词数。

4. **返回答案：**将每个查询的结果存储在一个列表 ans 中，并最终返回该列表作为函数的结果。