当前位置：首页 > news >正文

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

news 来源：原创 2024/9/29 17:34:52

给你一个下标从 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 = 0pre = [0] * (len(words))for i in range(len(words)):presum += nums[i]pre[i] = presumans = []for i in queries:count = 0if i[0] == 0:count = pre[i[1]]else:count = pre[i[1]] - pre[i[0] - 1]ans.append(count)return ans

**预处理：**首先，对给定的单词列表进行预处理，对于每个单词，检查其是否以元音字母开头和结尾。如果是，则将对应的 nums 数组的对应位置标记为 1，表示该位置的单词满足条件，否则标记为 0。
**前缀和：**然后，使用前缀和技巧来快速计算出满足条件的单词数。创建一个前缀和数组 pre，其中 pre[i] 表示从单词列表的开头到第 i 个单词（包括第 i 个单词）满足条件的单词数的累计和。遍历 nums 数组，并计算累计和，将结果存储在 pre 数组中。
**查询处理：**对于每个查询范围 [start, end]，我们可以利用前缀和数组 pre 来计算该范围内满足条件的单词数。如果查询范围的起始位置为 0，则直接取 pre[end] 作为答案；否则，我们可以通过计算 pre[end] - pre[start - 1] 来得到该范围内的满足条件的单词数。
**返回答案：**将每个查询的结果存储在一个列表 ans 中，并最终返回该列表作为函数的结果。