Prefix Sum IV: Prefix Sum in disguise

Sometimes a problem may not look like a Prefix Sum, but in reality it is. This is an example. Pretty much compute the prefix sum for each word and use that to calculate the difference between the indexes of the queries. Code is down below, cheers, ACC.

Count Vowel Strings in Ranges - LeetCode

2559. Count Vowel Strings in Ranges

Medium

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 <= 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

public int[] VowelStrings(string[] words, int[][] queries)
{
    int[] prefixSum = new int[words.Length];

    prefixSum[0] = StartEndVowel(words[0]) ? 1 : 0;
    for (int i = 1; i < words.Length; i++)
        prefixSum[i] = prefixSum[i - 1] + (StartEndVowel(words[i]) ? 1 : 0);

    int[] retVal = new int[queries.Length];
    for (int i = 0; i < queries.Length; i++)
        retVal[i] = prefixSum[queries[i][1]] - prefixSum[queries[i][0]] + (StartEndVowel(words[queries[i][0]]) ? 1 : 0);

    return retVal;
}

private bool StartEndVowel(string str)
{
    return !String.IsNullOrEmpty(str) && "aeiou".Contains(str[0]) && "aeiou".Contains(str[str.Length - 1]);
}