What is the optimal solution for 'Count Vowel Strings in Ranges'?

The optimal solution involves precomputing a prefix sum of words that start and end with vowels, which allows answering each query in constant time.

How do I approach range queries in this problem?

Use a prefix sum approach where each entry contains the count of words that meet the condition up to that index. Subtract values from the prefix sum array to answer range queries efficiently.

What should I focus on for the 'Array plus String' pattern?

Focus on efficiently managing string checks and optimizing range queries using array-based techniques like prefix sums.

How does the vowel-checking condition affect the solution?

By precomputing a binary array that marks words starting and ending with vowels, we can quickly compute the answer for any query range.

What are common mistakes to avoid in this problem?

Avoid inefficient brute-force solutions, incorrect handling of the prefix sum array, and errors in checking the vowel conditions for each word.

#2559

Medium

auto_awesome数组·string

LeetCode 题解工作台

统计范围内的元音字符串数

给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。每个查询 queries[i] = [l i , r i ] 会要求我们统计在 words 中下标在 l i 到 r i 范围内（包含这两个值）并且以元音开头和结尾的字符串的数目。返回一个整数数组，其中…

数组字符串前缀和

题目描述

给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。

每个查询 queries[i] = [l_i, r_i] 会要求我们统计在 words 中下标在 l_i 到 r_i 范围内（包含这两个值）并且以元音开头和结尾的字符串的数目。

返回一个整数数组，其中数组的第 i 个元素对应第 i 个查询的答案。

注意：元音字母是 'a'、'e'、'i'、'o' 和 'u' 。

示例 1：

输入：words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
输出：[2,3,0]
解释：以元音开头和结尾的字符串是 "aba"、"ece"、"aa" 和 "e" 。
查询 [0,2] 结果为 2（字符串 "aba" 和 "ece"）。
查询 [1,4] 结果为 3（字符串 "ece"、"aa"、"e"）。
查询 [1,1] 结果为 0 。
返回结果 [2,3,0] 。

示例 2：

输入：words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]
输出：[3,2,1]
解释：每个字符串都满足这一条件，所以返回 [3,2,1] 。

提示：

1 <= words.length <= 10⁵
1 <= words[i].length <= 40
words[i] 仅由小写英文字母组成
sum(words[i].length) <= 3 * 10⁵
1 <= queries.length <= 10⁵
0 <= queries[j][0] <= queries[j][1] < words.length

lightbulb

解题思路

方法一：预处理 + 二分查找

我们可以预处理出所有以元音开头和结尾的字符串的下标，按顺序记录在数组 $nums$ 中。

接下来，我们遍历每个查询 $(l, r)$ ，通过二分查找在 $nums$ 中找到第一个大于等于 $l$ 的下标 $i$ ，以及第一个大于 $r$ 的下标 $j$ ，那么当前查询的答案就是 $j - i$ 。

时间复杂度 $O(n + m \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $m$ 分别是数组 $words$ 和 $queries$ 的长度。

1

2

3

4

5

6

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        vowels = set("aeiou")
        nums = [i for i, w in enumerate(words) if w[0] in vowels and w[-1] in vowels]
        return [bisect_right(nums, r) - bisect_left(nums, l) for l, r in queries]

speed

复杂度分析

指标	值
时间	O(M + N)
空间	O(M)

psychology

面试官常问的追问

外企场景

question_mark
Candidate is able to implement the prefix sum approach to optimize range queries.
question_mark
Candidate correctly handles the constraints and performs preprocessing efficiently.
question_mark
Candidate understands the concept of vowel-checking and its application in this problem.

warning

常见陷阱

外企场景

error
Failing to initialize the prefix sum array correctly, especially with respect to boundary conditions.
error
Not efficiently checking whether a word starts and ends with a vowel, resulting in unnecessary time complexity.
error
Misunderstanding the problem constraints and attempting to solve it with a brute-force approach, leading to time limit exceeded errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of counting words starting and ending with vowels, count words starting with a vowel but ending with a consonant.
arrow_right_alt
Given a range, find the longest valid word within it that starts and ends with a vowel.
arrow_right_alt
Modify the problem to count strings containing vowels at any positions within the given ranges.

help

常见问题

外企场景

继续练习

#2391 收集垃圾的最少总时间 #2381 字母移位 II #2055 蜡烛之间的盘子