<p>You are given a <strong>0-indexed</strong> array of strings <code>words</code> and a 2D array of integers <code>queries</code>.</p>

<p>Each query <code>queries[i] = [l<sub>i</sub>, r<sub>i</sub>]</code> asks us to find the number of strings present in the range <code>l<sub>i</sub></code> to <code>r<sub>i</sub></code> (both <strong>inclusive</strong>) of <code>words</code> that start and end with a vowel.</p>

<p>Return <em>an array </em><code>ans</code><em> of size </em><code>queries.length</code><em>, where </em><code>ans[i]</code><em> is the answer to the </em><code>i</code><sup>th</sup><em> query</em>.</p>

<p><strong>Note</strong> that the vowel letters are <code>&#39;a&#39;</code>, <code>&#39;e&#39;</code>, <code>&#39;i&#39;</code>, <code>&#39;o&#39;</code>, and <code>&#39;u&#39;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;aba&quot;,&quot;bcb&quot;,&quot;ece&quot;,&quot;aa&quot;,&quot;e&quot;], queries = [[0,2],[1,4],[1,1]]
<strong>Output:</strong> [2,3,0]
<strong>Explanation:</strong> The strings starting and ending with a vowel are &quot;aba&quot;, &quot;ece&quot;, &quot;aa&quot; and &quot;e&quot;.
The answer to the query [0,2] is 2 (strings &quot;aba&quot; and &quot;ece&quot;).
to query [1,4] is 3 (strings &quot;ece&quot;, &quot;aa&quot;, &quot;e&quot;).
to query [1,1] is 0.
We return [2,3,0].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;a&quot;,&quot;e&quot;,&quot;i&quot;], queries = [[0,2],[0,1],[2,2]]
<strong>Output:</strong> [3,2,1]
<strong>Explanation:</strong> Every string satisfies the conditions, so we return [3,2,1].</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= words[i].length &lt;= 40</code></li>
	<li><code>words[i]</code> consists only of lowercase English letters.</li>
	<li><code>sum(words[i].length) &lt;= 3 * 10<sup>5</sup></code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= l<sub>i</sub> &lt;= r<sub>i</sub> &lt;&nbsp;words.length</code></li>
</ul>

from itertools import accumulate
class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        """
        Condition: strings that begin and end with a vowel
        vowels = ["a", "e", "i", "o", "u"]
        [0, 2] => "aba" and "ece" start and end with a vowel -> [2]
        [1, 4] => "ece", "aa" and "e" start and end with a vowel -> [3]
        [1, 1] => "bcb" does not begin / end with a vowel -> [0]
        final answer = [2, 3, 0]
        """
        if len(queries) == 0 or len(words) == 0:
            return []
        binary_array = []
        # words =   ["aba", "bcb", "ece", "aa", "e"]
        vowels = set("aeiou")
        binary_array = [1 if word and word[0] in vowels and word[-1] in vowels else 0 for word in words]
        # binary_array = [1, 0, 1, 1, 1]
        # prefix = [binary_array[0]] # [1]
        # for idx, item in enumerate(binary_array):
        #     if idx == 0: continue # We already covered this case
        #     prefix.append(prefix[idx-1] + item)
        prefix = list(accumulate(binary_array))
        # [1, 1, 2, 3, 4]
        # Now we have generated the prefix array. We can just cover all the ranges
        result = []
        # queries = [[0, 2], [1, 4], [1, 1]]
        for query in queries:
            l, r = query
            if l == 0:
                result.append(prefix[r])
            else:
                result.append(prefix[r] - prefix[l-1])
        return result
523