计算范围内的元音字符串

2559。计算范围内的元音字符串

难度：中等

主题：数组、字符串、前缀和

您将获得一个 0 索引 字符串单词数组和一个 2D 整数查询数组。

每个查询 requests[i] = [l_i, r_i] 要求我们找到 l_i 范围内存在的字符串数量r_i（包含两者）以元音开头和结尾的单词。

返回大小为querys.length的数组ans，其中ans[i]是第i^第查询的答案。

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

示例1：

• 输入： 单词 = ["aba","bcb","ece","aa","e"], 查询 = [[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：

• 输入： 单词 = ["a","e","i"], 查询 = [[0,2],[0,1],[2,2]]
• 输出： [3,2,1]
• 解释： 每个字符串都满足条件，所以我们返回 [3,2,1]。

约束：

• 1 5
• 1
• words[i] 仅由小写英文字母组成。
• sum(words[i].length) 5
• 1 5
• 0 i i

提示：

1. 预先计算以元音开头和结尾的字符串的前缀和。
2. 使用unordered_set来存储元音。
3. 检查字符串的第一个和最后一个字符是否出现在元音集中。
4. 减去范围 [l-1, r] 的前缀和即可找到以元音开头和结尾的字符串的数量。

解决方案：

我们可以按照以下步骤操作：

1. 检查元音字符串： 创建一个辅助函数来确定字符串是否以元音开头和结尾。
2. 预计算前缀和：使用前缀和数组来存储以元音开头和结尾的字符串的累积计数。
3. 回答查询：使用前缀和数组高效计算每个查询指定范围内此类字符串的数量。

让我们用 PHP 实现这个解决方案：2559。计算范围内的元音字符串

<?php /**
 * @param String[] $words
 * @param Integer[][] $queries
 * @return Integer[]
 */
function vowelStrings($words, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to check if a string starts and ends with a vowel
 *
 * @param $word
 * @return bool
 */
function isVowelString($word) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$words1 = ["aba", "bcb", "ece", "aa", "e"];
$queries1 = [[0, 2], [1, 4], [1, 1]];
print_r(countVowelStringsInRanges($words1, $queries1)); // Output: [2, 3, 0]

// Example 2
$words2 = ["a", "e", "i"];
$queries2 = [[0, 2], [0, 1], [2, 2]];
print_r(countVowelStringsInRanges($words2, $queries2)); // Output: [3, 2, 1]
?>

解释：

1. isVowelString 函数：

   • 检查字符串的第一个和最后一个字符是否为元音。
   • 使用 in_array 来确定字符是否在预定义的元音列表中。

2. 前缀和数组：

   • prefixSum[i] 存储直到索引 i-1 的元音字符串的累积计数。
   • 如果当前单词满足条件，则增加计数。

3. 查询解析：

   • 对于范围 [l, r]，元音字符串的数量为 prefixSum[r 1] - prefixSum[l]。

4. 效率：

   • 构造前缀和数组需要 O(n)，其中 n 是单词数。
   • 解决每个查询需要O(1)，使得整体复杂度O(n q)，其中q 是查询次数。

边缘情况：

• 所有字符串均以元音开头和结尾。
• 没有字符串以元音开头和结尾。
• 查询中的单元素范围。

这种方法有效地处理了问题的约束。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是计算范围内的元音字符串的详细内容。更多信息请关注PHP中文网其他相关文章！