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

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

🎯 问题描述

描述：
给你一个下标从 0 开始的字符串数组 words 和一个二维整数数组 queries。
对于每个查询 queries[i] = [li, ri]，请计算 words 中下标在 [li, ri] 范围内（包含两端）有多少个元音字符串。

元音字符串定义：

• 该字符串以元音字母开头 并且 以元音字母结尾。
• 元音字母包括：‘a’, ‘e’, ‘i’, ‘o’, ‘u’。

说明：

• 这是一个前缀和的经典应用场景。

• 核心策略：

  • 题目涉及多次区间求和查询。
  • 如果直接对每个查询遍历区间，时间复杂度为 $O(Q \cdot N)$，在数据量大时会超时。
  • 利用前缀和数组，我们可以先预处理出每个位置之前有多少个元音字符串。
  • 查询时，利用前缀和的差值在 $O(1)$ 时间内得到结果。

• 示例：

• 示例 1：

输入：words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
输出：[2,3,1]
解释：
- 元音字符串判断：
  - "aba": 开头'a', 结尾'a' -> 是 (1)
  - "bcb": 开头'b', 结尾'b' -> 否 (0)
  - "ece": 开头'e', 结尾'e' -> 是 (1)
  - "aa": 开头'a', 结尾'a' -> 是 (1)
  - "e": 开头'e', 结尾'e' -> 是 (1)
- 标记数组为：[1, 0, 1, 1, 1]
- queries[0] = [0, 2]: 对应 "aba", "bcb", "ece"。和为 1+0+1 = 2。
- queries[1] = [1, 4]: 对应 "bcb", "ece", "aa", "e"。和为 0+1+1+1 = 3。
- queries[2] = [1, 1]: 对应 "bcb"。和为 0。

💻 解题思路

思路1：前缀和 + 预处理

核心逻辑

1. 预处理标记：
   • 遍历 words 数组。
   • 对于每个单词，检查首字符和尾字符是否都在 “aeiou” 中。
   • 如果是，标记为 1；否则标记为 0。
2. 构建前缀和数组 pre：
   • pre[i+1] 表示 words[0] 到 words[i] 中元音字符串的总数量。
   • 递推公式：pre[i+1] = pre[i] + flag。
   • 注意 pre 数组长度为 n+1，且 pre[0] = 0，这样可以方便处理边界情况。
3. 处理查询：
   • 对于每个查询 [l, r]，利用前缀和性质计算区间和。
   • 结果 = pre[r+1] - pre[l]。
   • 这表示前 r+1 个单词的总数减去前 l 个单词的总数，剩下的就是区间 [l, r] 内的数量。

代码实现

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        n = len(words)
        m = len(queries)
        ans = []
        
        # 1. 构建前缀和数组
        # pre[i+1] 表示 words[0...i] 中元音字符串的数量
        pre = [0] * (n + 1)
        
        for i, s in enumerate(words):
            flag = 0
            # 判断首尾字符是否都是元音
            if s[0] in "aeiou" and s[-1] in "aeiou":
                flag = 1 # 是元音字符串
            
            # 累加前缀和
            pre[i+1] = pre[i] + flag
            
        # 2. 处理每个查询
        for l, r in queries:
            # 利用前缀和计算区间 [l, r] 的和
            # 结果 = (0到r的总和) - (0到l-1的总和)
            c = pre[r+1] - pre[l]
            ans.append(c)
            
        return ans

📊 性能分析

• 时间复杂度：$O(N + Q)$
  • 构建前缀和数组：$O(N)$，其中 $N$ 是 words 的长度。判断每个字符串首尾字符耗时 $O(1)$。
  • 处理查询：$O(Q)$，其中 $Q$ 是 queries 的长度。每个查询只需 $O(1)$ 时间进行减法运算。
  • 总体线性时间，非常高效。
• 空间复杂度：$O(N)$
  • 需要一个长度为 $N+1$ 的 pre 数组来存储前缀和。
  • 结果数组 ans 占用 $O(Q)$ 空间（通常不计入额外空间复杂度，因为是返回值）。

思考

1. 前缀和的定义技巧：

   • 我们定义 pre[i+1] 为前 i+1 个元素（下标 0 到 i）的满足条件的数量。
   • 这种定义方式（pre 长度比原数组多 1，且 pre[0]=0）是处理区间查询的标准技巧。
   • 它避免了处理 l=0 时的边界特判，因为 pre[0] 天然为 0。

2. 为什么使用前缀和？

   • 如果不使用前缀和，对于每个查询 [l, r]，我们需要遍历 words[l] 到 words[r]，耗时 $O(r-l+1)$。
   • 在最坏情况下（查询区间很大且查询次数多），总时间复杂度接近 $O(Q \cdot N)$。
   • 前缀和通过一次 $O(N)$ 的预处理，将每次查询降为 $O(1)$，极大地提高了效率。

3. 元音判断优化：

   • 代码中使用 s[0] in "aeiou"。在 Python 中，对于短字符串，这种查找是很快的。
   • 如果需要极致优化，可以将 “aeiou” 转换为集合 set('aeiou')，查找时间复杂度稳定为 $O(1)$。

4. 空间优化：

   • 如果输入数组 words 允许修改，或者我们不需要保留原始数据，其实可以用 words 数组本身来存储前缀和（如果类型允许）。
   • 但在本题中，为了代码清晰和安全性，开辟新的 pre 数组是最佳选择。