统计范围内的元音字符串数
难度:
标签:
题目描述
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.length
代码结果
运行时间: 63 ms, 内存: 46.7 MB
/*
* Problem: Similar to the previous solution, but using Java Streams for a more functional approach.
* Approach:
* 1. Define a set of vowels.
* 2. Use streams to calculate the prefix sum array.
* 3. For each query, calculate the result using prefix sum array.
*/
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;
public class VowelWordsStream {
public int[] vowelStrings(String[] words, int[][] queries) {
Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');
int[] prefix = IntStream.range(0, words.length)
.map(i -> isVowelWord(words[i], vowels) ? 1 : 0)
.toArray();
int[] cumulativePrefix = new int[words.length + 1];
IntStream.range(0, prefix.length)
.forEach(i -> cumulativePrefix[i + 1] = cumulativePrefix[i] + prefix[i]);
return IntStream.range(0, queries.length)
.map(i -> cumulativePrefix[queries[i][1] + 1] - cumulativePrefix[queries[i][0]])
.toArray();
}
private boolean isVowelWord(String word, Set<Character> vowels) {
return vowels.contains(word.charAt(0)) && vowels.contains(word.charAt(word.length() - 1));
}
}解释
方法:
此题解使用了前缀和的方法来解决问题。首先，遍历 words 数组并构建一个前缀和数组 pre。在这个数组中，每个元素 pre[i] 表示从 words[0] 到 words[i-1] 的范围内，以元音开头和结尾的字符串的数量。如果当前字符串 word 以元音开头和结尾，则将前一个元素的前缀和加一；否则，保持前缀和不变。构建完前缀和数组后，对于每个查询 [l, r]，可以通过计算 pre[r+1] - pre[l] 来得到下标范围 l 到 r 内以元音开头和结尾的字符串的数量。这样可以快速回答查询，避免重复计算。
时间复杂度:
O(n + q)
空间复杂度:
O(n + q)
代码细节讲解
🦆
为何在构建前缀和数组时，要初始化`pre`数组为`[0]`，而非空数组或其他初始值？
▷🦆
在题解中提到的前缀和数组`pre[i]`表示的是`从words[0]到words[i-1]`的范围内以元音开头和结尾的字符串数量，那么为什么查询时使用`pre[r+1] - pre[l]`而不是`pre[r] - pre[l-1]`来得到答案？
▷🦆
代码中判断字符串是否以元音开头和结尾的条件是`word[0] in vowels and word[-1] in vowels`，这种方式是否考虑了字符串长度为1的情况？
▷🦆
如果`words`数组为空，或者`queries`数组为空，该解决方案是否还会正确运行？需要做哪些额外的边界检查？
▷