统计范围内的元音字符串数

标签: 数组 字符串 前缀和

难度: Medium

给你一个下标从 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

Submission

运行时间: 63 ms

内存: 46.7 MB

from typing import List
class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        vowels = 'aeiou'
        pre = [0]
        for word in words:
            if word[0] in vowels and word[-1] in vowels:
                pre.append(pre[-1]+1)
            else:
                pre.append(pre[-1])

        ans = []
        for l,r in queries:
            ans.append(pre[r+1]-pre[l])
        return ans

Explain

此题解使用了前缀和的方法来解决问题。首先，遍历 words 数组并构建一个前缀和数组 pre。在这个数组中，每个元素 pre[i] 表示从 words[0] 到 words[i-1] 的范围内，以元音开头和结尾的字符串的数量。如果当前字符串 word 以元音开头和结尾，则将前一个元素的前缀和加一；否则，保持前缀和不变。构建完前缀和数组后，对于每个查询 [l, r]，可以通过计算 pre[r+1] - pre[l] 来得到下标范围 l 到 r 内以元音开头和结尾的字符串的数量。这样可以快速回答查询，避免重复计算。

时间复杂度: O(n + q)

空间复杂度: O(n + q)

from typing import List

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        vowels = 'aeiou'  # 元音字母集
        pre = [0]  # 初始化前缀和数组
        for word in words:  # 遍历每个单词
            if word[0] in vowels and word[-1] in vowels:  # 判断单词是否以元音开头和结尾
                pre.append(pre[-1]+1)  # 若是，则前缀和加一
            else:
                pre.append(pre[-1])  # 否则，前缀和不变

        ans = []  # 初始化答案数组
        for l, r in queries:  # 处理每个查询
            ans.append(pre[r+1]-pre[l])  # 通过前缀和快速计算结果
        return ans

Explore

在构建前缀和数组时，初始化`pre`数组为`[0]`是为了方便计算从任何位置开始至任何位置结束的区间和。这个初始化为0的元素代表的是在任何字符串加入前的初始状态，即没有任何字符串时的前缀和。如果不初始化为`[0]`而是开始为空数组，那么在计算某些查询如`[0, r]`时，将无法直接使用`pre[r+1]`，因为`pre[0]`这个必要的基准点不存在。此外，初始化为0也避免了在数组非空但未包含任何符合条件的字符串时的错误累加。

这是因为`pre[i]`实际上代表的是从`words[0]`到`words[i-1]`（闭区间）的计数，所以`pre[r+1]`实际上是代表从`words[0]`到`words[r]`的计数。为了得到从`words[l]`到`words[r]`的计数，我们需要使用`pre[r+1]`减去`pre[l]`（代表从`words[0]`到`words[l-1]`的计数），这样就准确地得到了`l`到`r`区间的计数。如果使用`pre[r] - pre[l-1]`，则会漏掉`words[r]`这个位置的计数（如果它符合条件）。

是的，这种判断方式考虑了字符串长度为1的情况。当字符串长度为1时，`word[0]`和`word[-1]`都指向这个唯一的字符。因此，如果这个字符是元音，那么这个长度为1的字符串同时满足以元音开头和结尾的条件。

如果`words`数组为空，则`pre`数组仅包含初始的0，不会有任何增加的元素。在这种情况下，任何查询都应返回0，因为没有字符串符合条件。代码应当能够处理这种情况，因为`pre[r+1] - pre[l]`在r和l有效时返回0。如果`queries`数组为空，则最终返回的答案数组也应为空，没有任何额外的计算。确保解决方案正确处理这些情况，主要的边界检查应包括确保在访问`pre`数组元素前，其索引是有效的，避免越界错误。