You are given a 0-indexed array of strings words
and a 2D array of integers queries
.
Each query queries[i] = [li, ri]
asks us to find the number of strings present in the range li
to ri
(both inclusive) of words
that start and end with a vowel.
Return an array ans
of size queries.length
, where ans[i]
is the answer to the i
th query.
Note that the vowel letters are 'a'
, 'e'
, 'i'
, 'o'
, and 'u'
.
Example 1:
Input: words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]] Output: [2,3,0] Explanation: The strings starting and ending with a vowel are "aba", "ece", "aa" and "e". The answer to the query [0,2] is 2 (strings "aba" and "ece"). to query [1,4] is 3 (strings "ece", "aa", "e"). to query [1,1] is 0. We return [2,3,0].
Example 2:
Input: words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]] Output: [3,2,1] Explanation: Every string satisfies the conditions, so we return [3,2,1].
Constraints:
1 <= words.length <= 105
1 <= words[i].length <= 40
words[i]
consists only of lowercase English letters.sum(words[i].length) <= 3 * 105
1 <= queries.length <= 105
0 <= li <= ri < words.length
统计范围内的元音字符串数。
给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。
每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内(包含 这两个值)并且以元音开头和结尾的字符串的数目。
返回一个整数数组,其中数组的第 i 个元素对应第 i 个查询的答案。
注意:元音字母是 'a'、'e'、'i'、'o' 和 'u' 。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/count-vowel-strings-in-ranges
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路是前缀和。首先我们需要一个与 words 数组等长的数组 goods 记录哪些单词满足以元音开头和结尾这个条件,遍历 words 数组的时候,判断每一个单词 words[i] 是否满足条件,如果是,则在 goods[i] 处标记为 1。我们还需要另外一个数组 presums 记录 goods 数组的前缀和。最后我们通过 presums 快速地找到每一个 query 的答案。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public int[] vowelStrings(String[] words, int[][] queries) { 3 int[] good = new int[words.length]; 4 for (int i = 0; i < words.length; i++) { 5 if (helper(words[i])) { 6 good[i] = 1; 7 } 8 } 9 10 int[] presum = new int[words.length + 1]; 11 presum[0] = good[0]; 12 for (int i = 0; i < words.length; i++) { 13 presum[i + 1] = presum[i] + good[i]; 14 } 15 16 int n = queries.length; 17 int[] res = new int[n]; 18 for (int i = 0; i < n; i++) { 19 int start = queries[i][0]; 20 int end = queries[i][1]; 21 res[i] = presum[end + 1] - presum[start]; 22 } 23 return res; 24 } 25 26 private boolean helper(String word) { 27 Set<Character> set = new HashSet<>(); 28 set.add('a'); 29 set.add('e'); 30 set.add('i'); 31 set.add('o'); 32 set.add('u'); 33 if (set.contains(word.charAt(0)) && set.contains(word.charAt(word.length() - 1))) { 34 return true; 35 } 36 return false; 37 } 38 }
- LeetCode Strings Ranges Count Vowelleetcode strings ranges count leetcode greatest divisor strings equivalent leetcode whether strings leetcode minimum strings delete unreachable undirected leetcode count occurrence leetcode common count leetcode target count pairs leetcode number count pairs communicate leetcode servers count leetcode average subtree count