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 中,并最终返回该列表作为函数的结果。

相关推荐

  1. 算法时间复杂空间复杂

    2024-06-11 08:40:02       10 阅读
  2. 时间复杂空间复杂

    2024-06-11 08:40:02       31 阅读
  3. 时间复杂空间复杂

    2024-06-11 08:40:02       11 阅读
  4. 时间复杂空间复杂

    2024-06-11 08:40:02       7 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-06-11 08:40:02       8 阅读
  2. 【Python教程】压缩PDF文件大小

    2024-06-11 08:40:02       9 阅读
  3. 通过文章id递归查询所有评论(xml)

    2024-06-11 08:40:02       10 阅读

热门阅读

  1. 【Python】易错点——数组;列表;内存分配

    2024-06-11 08:40:02       8 阅读
  2. NLP--朴素贝叶斯

    2024-06-11 08:40:02       5 阅读
  3. vue基础

    vue基础

    2024-06-11 08:40:02      3 阅读
  4. 归并排序!

    2024-06-11 08:40:02       7 阅读