。単語のサブセット

916。単語のサブセット

難易度: 中

トピック: 配列、ハッシュ テーブル、文字列

2 つの文字列配列 Word1 と Words2 が与えられています。

文字列 b 内のすべての文字が多重度を含めて a に出現する場合、文字列 b は文字列 a のサブセットです。

• たとえば、「wrr」は「warrior」のサブセットですが、「world」のサブセットではありません。

words2 のすべての文字列 b について、b が a のサブセットである場合、words1 の文字列 a は ユニバーサルです。

word1 内のすべての ユニバーサル 文字列の配列を 返します。回答は任意の順序で返すことができます。

例 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] は英小文字のみで構成されます。
• 単語 1 のすべての文字列は 一意です。

解決策:

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. words2 の頻度マップの構築: Words2 内の各単語をループし、各文字の頻度を計算します。 Words2 のすべての単語にわたって、各文字に必要な最大頻度を追跡します。

2. 単語 1 の単語のチェック: 単語 1 の各単語について、各文字の頻度を計算し、単語 2 の必要な頻度と比較します。単語がすべての文字の要件を満たしている場合、その単語は普遍的であるとみなされます。

3. 結果: すべての汎用単語を結果配列に格納し、最後に返します。

時間計算量:

• words2 の頻度マップの構築: O(n * m)、n は Words2 の長さ、m は Words2 内の単語の平均長です。
• 単語 1 のチェック: O(k * m)、ここで、k は単語 1 の長さ、m は単語 1 内の単語の平均長です。
• 合計時間計算量は約 O(n * m k * m) です。

このアプローチにより、各単語を効率的にチェックし、問題の制約を確実に満たすことができます。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。単語のサブセットの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。