。單字子集

916。單字子集

難度：中

主題：陣列、雜湊表、字串

給你兩個字串陣列word1和words2。

如果 b 中的每個字母都出現在 a 中，則字串 b 是字串 a 的 子集。

• 例如，「wrr」是「warrior」的子集，但不是「world」的子集。

words1 中的字串 a 是通用如果對於words2 中的每個字串 b，b 是 a 的子集。

傳回words1中所有通用字串的陣列。您可以按任何順序回答案。

範例1：

• 輸入：words1 = ["amazon","apple","facebook","google","leetcode"]，words2 = ["e","o"]
• 輸出： ["facebook","google","leetcode"]

範例2：

• 輸入：words1 = ["amazon","apple","facebook","google","leetcode"]，words2 = ["l","e"]
• 輸出： ["apple","google","leetcode"]

約束：

• 1 4
• 1
• Words1[i] 和 Words2[i] 僅由小寫英文字母組成。
• words1 的所有字串都是唯一。

解：

我們需要辨識words1中「通用」的單詞，這表示words2中的每個字串都是words1中單字的子集。

方法：

1. 統計單字中字元的出現頻率2：

   • 首先，我們需要確定words2 中所有字串中每個字元的最大計數。這為我們提供了每個字元作為子集所需的出現次數。

2. 檢查words1中的每個單字：

   • 對於words1中的每個單詞，計算每個字符的頻率。
   • 如果words1中的單字中的字元數滿足或超過words2中所需的計數，則該單字是通用的。

3. 回傳通用字：

   • 檢查完words1中的所有單字後，回傳通用的單字。

讓我們用 PHP 實作這個解：916。單字子集

<?php /**
 * @param String[] $words1
 * @param String[] $words2
 * @return String[]
 */
function wordSubsets($words1, $words2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$words1 = ["amazon", "apple", "facebook", "google", "leetcode"];
$words2 = ["e", "o"];
print_r(wordSubsets($words1, $words2));  // Output: ["facebook", "google", "leetcode"]

$words2 = ["l", "e"];
print_r(wordSubsets($words1, $words2));  // Output: ["apple", "google", "leetcode"]
?>

解釋：

1. 為wo​​rds2建立頻率圖：我們循環遍歷words2中的每個單字併計算每個字元的頻率。我們追蹤 Words2 中所有單字中每個字元所需的最大頻率。

2. 檢查words1單字：對於words1中的每個單字，我們計算每個字元的頻率並將其與words2中所需的頻率進行比較。如果該單字滿足所有字元的要求，則被認為是通用的。

3. 結果：我們將所有通用單字儲存在結果陣列中並在最後返回。

時間複雜度：

• 建構words2的頻率圖： O(n * m)，其中n是words2的長度，m是words2中單字的平均長度。
• 檢查單字1： O(k * m)，其中k是單字1的長度，m是單字1中單字的平均長度。
• 總時間複雜度約為O(n * m k * m).

這種方法確保我們有效地檢查每個單字並滿足問題的限制。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。單字子集的詳細內容。更多資訊請關注PHP中文網其他相關文章！