LeetCode元音字符串统计：前缀和算法优化

1. 问题背景与需求拆解

今天遇到一道LeetCode周赛题目（2559题），要求统计给定字符串数组中满足特定条件的元音字符串数量。具体来说，需要处理两类输入：

• 一个字符串数组words，每个元素都是一个单词
• 多个查询区间queries，每个查询给出起始和结束索引

判断条件很明确：统计words数组中从queries[i][0]到queries[i][1]区间内，所有以元音字母开头且结尾的字符串数量。元音字母定义为a、e、i、o、u这五个字母（大小写敏感）。

注意：题目中的区间是闭区间，包含两端点。例如查询[1,3]需要检查words[1]、words[2]、words[3]这三个字符串。

2. 核心算法设计思路

2.1 暴力解法分析

最直观的解法是对于每个查询，遍历区间内的每个字符串，逐个检查首尾字符：

python复制def is_vowel(c):
    return c in {'a','e','i','o','u'}

def count_vowel_strings(words, queries):
    res = []
    for l, r in queries:
        cnt = 0
        for i in range(l, r+1):
            word = words[i]
            if len(word) > 0 and is_vowel(word[0]) and is_vowel(word[-1]):
                cnt += 1
        res.append(cnt)
    return res

时间复杂度：O(Q*N)，其中Q是查询次数，N是平均查询区间长度。当Q和N都很大时（比如1e5量级），这种解法会超时。

2.2 前缀和优化方案

观察到查询操作是静态的（words数组不变），可以采用前缀和预处理：

1. 预处理一个前缀和数组prefix，其中prefix[i]表示words[0..i-1]中满足条件的字符串数量
2. 对于查询[l,r]，结果就是prefix[r+1] - prefix[l]

实现步骤：

python复制def build_prefix(words):
    prefix = [0]*(len(words)+1)
    for i in range(1, len(words)+1):
        word = words[i-1]
        valid = 1 if (len(word) > 0 and is_vowel(word[0]) and is_vowel(word[-1])) else 0
        prefix[i] = prefix[i-1] + valid
    return prefix

def count_vowel_strings(words, queries):
    prefix = build_prefix(words)
    return [prefix[r+1] - prefix[l] for l, r in queries]

时间复杂度：预处理O(N)，查询O(Q)，整体O(N+Q)。空间复杂度O(N)。

3. 实现细节与边界处理

3.1 元音判断优化

元音判断可以有以下几种实现方式：

python复制# 方式1：集合查找
def is_vowel(c):
    return c in {'a','e','i','o','u'}

# 方式2：字符串查找
def is_vowel(c):
    return c in 'aeiou'

# 方式3：位运算（ASCII码特化）
def is_vowel(c):
    mask = (1 << ord('a')) | (1 << ord('e')) | (1 << ord('i')) | (1 << ord('o')) | (1 << ord('u'))
    return (1 << ord(c)) & mask

实测在Python中方式2最快，因为字符串的in操作有特殊优化。

3.2 空字符串处理

题目没有明确说明空字符串的情况，但根据示例判断：

• 空字符串""的首尾字符不存在，因此不算作元音字符串
• 实现时需要添加长度检查：len(word) > 0

3.3 前缀和数组的索引设计

前缀和数组通常有两种索引方式：

1. prefix[i]表示words[0..i]的和（包含i）
2. prefix[i]表示words[0..i-1]的和（不包含i）

我们选择第二种方式，因为：

• 计算区间和时公式更统一：[l,r]区间和=prefix[r+1]-prefix[l]
• 与Python的切片语义一致（words[l:r+1]）

4. 复杂度分析与优化对比

4.1 时间复杂度对比

当N=1e5，Q=1e5时：

• 暴力法：1e10次操作（不可接受）
• 前缀和：2e5次操作（毫秒级）

4.2 空间复杂度对比

前缀和方法需要额外的O(N)空间存储前缀和数组。在大多数情况下这是可以接受的，因为：

• 现代计算机内存充足
• 前缀和数组元素可以是32位整数（每个元素4字节）
• 对于N=1e5，只需要约400KB内存

5. 测试用例设计

完整的测试应该包含以下场景：

python复制test_cases = [
    # 常规情况
    (["aba","bcb","ece","aa","e"], [[0,2],[1,4],[1,1]], [2,3,0]),
    # 空字符串
    (["","a","e",""], [[0,2],[1,3]], [1,1]),
    # 单个字符
    (["a","b","c","d","e"], [[0,4]], [2]),
    # 全部不符合
    (["hello","world","cpp","python"], [[0,3]], [0]),
    # 全部符合
    (["aa","ee","ii"], [[0,2]], [3]),
]

6. 语言特性应用

6.1 C++实现要点

cpp复制vector<int> countVowelStrings(vector<string>& words, vector<vector<int>>& queries) {
    int n = words.size();
    vector<int> prefix(n+1, 0);
    for(int i=1; i<=n; ++i) {
        const auto& w = words[i-1];
        bool valid = !w.empty() && isVowel(w.front()) && isVowel(w.back());
        prefix[i] = prefix[i-1] + valid;
    }
    
    vector<int> res;
    for(const auto& q : queries) {
        res.push_back(prefix[q[1]+1] - prefix[q[0]]);
    }
    return res;
}

bool isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

6.2 Python实现技巧

使用生成器表达式简化代码：

python复制def count_vowel_strings(words, queries):
    prefix = [0]
    for w in words:
        prefix.append(prefix[-1] + (len(w) > 0 and w[0] in 'aeiou' and w[-1] in 'aeiou'))
    return [prefix[r+1] - prefix[l] for l, r in queries]

7. 同类问题扩展

前缀和技巧还可以解决以下类似问题：

1. 区间和查询（303. Range Sum Query - Immutable）
2. 二维区域和检索（304. Range Sum Query 2D - Immutable）
3. 统计优美子数组（1248. Count Number of Nice Subarrays）
4. 和为K的子数组（560. Subarray Sum Equals K）

这类问题的共同特点是：

• 数据静态不变
• 需要频繁查询某个区间的统计量
• 统计量可以表示为两个前缀结果的差值

8. 实际工程中的应用场景

前缀和技术在实际工程中应用广泛：

1. 实时数据统计：如统计过去1小时/24小时的请求量
2. 金融领域：计算股票区间收益率
3. 图像处理：计算图像子矩阵的像素和（积分图算法）
4. 推荐系统：统计用户近期行为次数

以Web服务器日志分析为例：

python复制# 预处理每小时请求数的前缀和
def build_hourly_prefix(logs):
    prefix = [0]*(24+1)
    for hour in range(1, 25):
        prefix[hour] = prefix[hour-1] + logs[hour-1]
    return prefix

# 查询2:00-5:00的请求量
def query_requests(prefix, start, end):
    return prefix[end+1] - prefix[start]

9. 常见错误与调试技巧

9.1 索引越界问题

在实现前缀和时容易出现的错误：

1. 忘记处理空查询列表
2. 查询的右边界超出words数组范围
3. 前缀和数组大小应为len(words)+1

调试方法：

• 打印前缀和数组内容
• 对每个查询先检查边界：assert 0 <= l <= r < len(words)

9.2 元音判断错误

常见错误包括：

1. 忘记处理大小写（题目通常明确大小写敏感）
2. 错误判断空字符串
3. 元音字母遗漏（如忘记包含'u'）

测试用例：

python复制assert is_vowel('a') == True
assert is_vowel('E') == False  # 除非题目说明不区分大小写
assert is_vowel('') == False   # 边界情况

10. 性能优化进阶

对于超大规模数据（N>1e7），可以考虑：

1. 并行计算前缀和：
   • 将数组分块
   • 每块独立计算局部前缀和
   • 合并时调整偏移量
2. 使用位压缩：
   • 用1bit表示每个单词是否满足条件
   • 然后计算popcount（统计1的个数）
3. SIMD指令优化：
   • 使用AVX2指令并行处理多个字符判断

示例（C++ SIMD实现）：

cpp复制#include <immintrin.h>

// 使用SSE4.2指令集加速元音判断
__m128i vowels = _mm_setr_epi8('a','e','i','o','u',0,0,0,0,0,0,0,0,0,0,0);

bool isVowelSIMD(char c) {
    __m128i v = _mm_set1_epi8(c);
    __m128i cmp = _mm_cmpeq_epi8(v, vowels);
    return _mm_movemask_epi8(cmp) != 0;
}

11. 不同语言的实现差异

11.1 Java实现注意点

Java中使用ArrayList会比数组慢，建议：

java复制int[] prefix = new int[words.length + 1];
for(int i=0; i<words.length; i++) {
    String w = words[i];
    prefix[i+1] = prefix[i] + (w.length()>0 && isVowel(w.charAt(0)) && isVowel(w.charAt(w.length()-1)) ? 1 : 0);
}

11.2 JavaScript优化

避免频繁的字符串操作：

javascript复制function countVowelStrings(words, queries) {
    const isVowel = c => 'aeiou'.includes(c);
    const prefix = [0];
    words.forEach(w => {
        const valid = w.length > 0 && isVowel(w[0]) && isVowel(w[w.length-1]) ? 1 : 0;
        prefix.push(prefix[prefix.length-1] + valid);
    });
    return queries.map(([l,r]) => prefix[r+1] - prefix[l]);
}

12. 单元测试与验证

完整的单元测试应该包含：

1. 常规功能测试
2. 边界条件测试（空输入、单个元素等）
3. 性能测试（大数据量）
4. 随机测试（自动生成测试用例）

Python示例：

python复制import random
import unittest

class TestSolution(unittest.TestCase):
    def test_random_cases(self):
        for _ in range(100):
            n = random.randint(1, 100)
            words = [''.join(random.choices('abcdefghijklmnopqrstuvwxyz', 
                     k=random.randint(0, 10))) for _ in range(n)]
            q = random.randint(1, 100)
            queries = [[random.randint(0, n-1), random.randint(0, n-1)] 
                      for _ in range(q)]
            queries = [[min(a,b), max(a,b)] for a,b in queries]
            
            # 对比暴力法和前缀和法结果是否一致
            expected = brute_force(words, queries)
            actual = count_vowel_strings(words, queries)
            self.assertEqual(expected, actual)

13. 代码风格与可读性

好的实现应该：

1. 将元音判断抽离为独立函数
2. 为前缀和数组添加注释说明索引含义
3. 使用有意义的变量名（如用valid代替tmp）
4. 保持一致的代码风格（缩进、空格等）

示例：

python复制def count_vowel_strings(words, queries):
    """统计区间内首尾都是元音的字符串数量
    
    Args:
        words: List[str], 字符串数组
        queries: List[List[int]], 查询区间列表
        
    Returns:
        List[int], 每个查询的结果
    """
    # prefix[i]表示前i个元素中满足条件的数量（i从0开始）
    prefix = [0] * (len(words) + 1)
    for i, word in enumerate(words):
        # 判断当前单词是否满足条件
        is_valid = (len(word) > 0 and 
                   is_vowel(word[0]) and 
                   is_vowel(word[-1]))
        prefix[i+1] = prefix[i] + (1 if is_valid else 0)
    
    # 处理所有查询
    return [prefix[r+1] - prefix[l] for l, r in queries]

14. 可视化辅助理解

对于教学目的，可以绘制前缀和示意图：

code复制words = ["aba","bcb","ece","aa","e"]
valid = [  1,    0,    1,   1,   1 ]  # 是否满足条件
prefix= [0, 1, 1, 2, 3, 4]  # 前缀和数组

查询[1,4]：
prefix[5] - prefix[1] = 4 - 1 = 3
对应"bcb","ece","aa","e"中满足的有3个

15. 相关LeetCode题目推荐

1. 303. Range Sum Query - Immutable
2. 304. Range Sum Query 2D - Immutable
3. 325. Maximum Size Subarray Sum Equals k
4. 560. Subarray Sum Equals K
5. 1248. Count Number of Nice Subarrays
6. 1314. Matrix Block Sum
7. 1524. Number of Sub-arrays With Odd Sum

这些题目都使用了前缀和技巧的变种，建议按顺序练习以掌握不同应用场景。