計算範圍內的元音字串

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中文網其他相關文章！