Medium

题目描述

给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries。

每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内（包含 li 和 ri）并且以元音开头和结尾的字符串的数目。

返回一个整数数组 ans，其中 ans[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 <= 10^5
  • 1 <= words[i].length <= 40
  • words[i] 仅由小写英文字母组成
  • sum(words[i].length) <= 3 * 10^5
  • 1 <= queries.length <= 10^5
  • 0 <= li <= ri < words.length

解题思路

这道题要求统计指定范围内以元音开头和结尾的字符串数量。由于有多次查询，我们需要优化查询效率。

核心思路：前缀和

  1. 预处理阶段：遍历所有字符串，对于每个字符串判断是否同时以元音开头和结尾
  2. 构建前缀和数组：创建一个前缀和数组，其中 prefix[i] 表示从索引 0 到 i-1 的范围内满足条件的字符串数量
  3. 快速查询：对于查询 [l, r]，答案就是 prefix[r+1] - prefix[l]

判断元音的方法：

  • 使用集合存储所有元音字符，便于快速查找
  • 检查字符串的第一个和最后一个字符是否都在元音集合中

时间复杂度优化：

  • 预处理：O(n)，其中 n 是字符串数组长度
  • 每次查询：O(1)
  • 总体：O(n + q)，其中 q 是查询次数

这种前缀和的方法将原本 O(q × n) 的暴力查询优化为 O(n + q)，在查询次数较多时效果显著。

代码实现

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
        int n = words.size();
        vector<int> prefix(n + 1, 0);
        
        // 构建前缀和数组
        for (int i = 0; i < n; i++) {
            string& word = words[i];
            bool isVowelString = vowels.count(word[0]) && vowels.count(word.back());
            prefix[i + 1] = prefix[i] + (isVowelString ? 1 : 0);
        }
        
        vector<int> result;
        for (auto& query : queries) {
            int l = query[0], r = query[1];
            result.push_back(prefix[r + 1] - prefix[l]);
        }
        
        return result;
    }
};

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        n = len(words)
        prefix = [0] * (n + 1)
        
        # 构建前缀和数组
        for i in range(n):
            word = words[i]
            is_vowel_string = word[0] in vowels and word[-1] in vowels
            prefix[i + 1] = prefix[i] + (1 if is_vowel_string else 0)
        
        result = []
        for l, r in queries:
            result.append(prefix[r + 1] - prefix[l])
        
        return result

public class Solution {
    public int[] VowelStrings(string[] words, int[][] queries) {
        HashSet<char> vowels = new HashSet<char> {'a', 'e', 'i', 'o', 'u'};
        int n = words.Length;
        int[] prefix = new int[n + 1];
        
        // 构建前缀和数组
        for (int i = 0; i < n; i++) {
            string word = words[i];
            bool isVowelString = vowels.Contains(word[0]) && vowels.Contains(word[word.Length - 1]);
            prefix[i + 1] = prefix[i] + (isVowelString ? 1 : 0);
        }
        
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int l = queries[i][0], r = queries[i][1];
            result[i] = prefix[r + 1] - prefix[l];
        }
        
        return result;
    }
}

var vowelStrings = function(words, queries) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    const n = words.length;
    const prefix = new Array(n + 1).fill(0);
    
    // 构建前缀和数组
    for (let i = 0; i < n; i++) {
        const word = words[i];
        const isVowelString = vowels.has(word[0]) && vowels.has(word[word.length - 1]);
        prefix[i + 1] = prefix[i] + (isVowelString ? 1 : 0);
    }
    
    const result = [];
    for (const [l, r] of queries) {
        result.push(prefix[r + 1] - prefix[l]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n + q)，其中 n 是字符串数组长度，q 是查询次数
空间复杂度O(n)，用于存储前缀和数组

相关题目