题目描述
给你一个下标从 0 开始的字符串数组 words
以及一个二维整数数组 queries
。
每个查询 queries[i] = [l_i, r_i]
会要求我们统计在 words
中下标在 l_i
到 r_i
范围内(包含 这两个值)并且以元音开头和结尾的字符串的数目。
返回一个整数数组,其中数组的第 i
个元素对应第 i
个查询的答案。
注意:元音字母是 'a'
、'e'
、'i'
、'o'
和 'u'
。
样例
输入: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]。
输入: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 <= queries[j][0] <= queries[j][1] < words.length
算法
(前缀和) $O(n + q)$
- 求出所有前缀中,符合条件的字符串的个数。
- 对于每个询问区间,通过两个前缀和相减得到答案。
时间复杂度
- 预处理前缀和的时间复杂度为 $O(n)$。
- 每个询问仅需要常数的时间。
- 故总时间复杂度为 $O(n + q)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储前缀和数组。
C++ 代码
class Solution {
private:
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
public:
vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
const int n = words.size();
vector<int> p(n + 1);
p[0] = 0;
for (int i = 1; i <= n; i++)
p[i] = p[i - 1] +
(isVowel(words[i - 1][0]) && isVowel(words[i - 1].back()));
vector<int> ans;
for (const auto &q : queries)
ans.push_back(p[q[1] + 1] - p[q[0]]);
return ans;
}
};