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 ith 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 <= 1051 <= words[i].length <= 40words[i] consists only of lowercase English letters.sum(words[i].length) <= 3 * 1051 <= queries.length <= 1050 <= li <= ri < words.lengthThis approach processes each query independently by iterating through the specified range of the words list, checking if each word both starts and ends with a vowel. This is a straightforward approach with a complexity that depends on both the number of queries and the length of the ranges.
In C, we define a helper function is_vowel to check for vowels. The main function vowelStringsQueries iterates over each query, checks the specified range, and counts valid words using the helper function count_vowel_strings. The results are stored and returned in an integer array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(Q * L), where Q is the number of queries and L is the average number of words per query range.
Space Complexity: O(1), aside from the result array space.
This approach seeks to improve efficiency by using a prefix sum array. In this approach, we first preprocess the words list to compute an array that stores the cumulative count of valid words up to each index. With this preprocessed information, each query can be answered in constant time.
In C, we first construct a prefix sum array that stores the cumulative count of valid words. Each query consists of quickly subtracting prefix sums to determine the number of valid words within the desired range, minimizing redundant calculations.
C++
Java
Python
C#
JavaScript
Time Complexity: O(W + Q), where W is the number of words and Q is the number of queries.
Space Complexity: O(W) for storing the prefix sum.
| Approach | Complexity |
|---|---|
| Direct Iteration for Each Query | Time Complexity: O(Q * L), where Q is the number of queries and L is the average number of words per query range. |
| Prefix Sum Array | Time Complexity: O(W + Q), where W is the number of words and Q is the number of queries. |
Count Vowel Strings in Ranges - Leetcode 2559 - Python • NeetCodeIO • 7,973 views views
Watch 9 more video solutions →Practice Count Vowel Strings in Ranges with our built-in code editor and test cases.
Practice on FleetCode