【Leetcode】2559. Count Vowel Strings in Ranges

题目地址：

https://leetcode.com/problems/count-vowel-strings-in-ranges/description/

给定一个长n nn的字符串列表w ww，再给定一系列询问，每次询问提供两个数l , r , l ≤ r l,r,l\le rl,r,l≤r，问w [ l : r ] w[l:r]w[l:r]有多少个字符串以元音开头和结尾。

前缀和。代码如下：

classSolution{public:vector<int>vowelStrings(vector<string>&ws,vector<vector<int>>&qs){vector<int>sum(ws.size()+1);staticconstexprautof=[](charch){returnch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u';};for(inti=0;i<ws.size();i++){auto&s=ws[i];sum[i+1]=sum[i]+(f(s[0])&&f(s.back()));}vector<int>res;res.reserve(qs.size());for(auto&v:qs)res.push_back(sum[v[1]+1]-sum[v[0]]);returnres;}};

时间复杂度O ( n + l q ) O(n+l_q)O(n+lq​)，空间O ( n ) O(n)O(n)。