. Subset Perkataan

916. Subset Perkataan

Kesukaran: Sederhana

Topik: Tatasusunan, Jadual Hash, Rentetan

Anda diberi dua tatasusunan rentetan perkataan1 dan perkataan2.

Rentetan b ialah subset rentetan a jika setiap huruf dalam b berlaku dalam kepelbagaian termasuk.

• Sebagai contoh, "wrr" ialah subset "pahlawan" tetapi bukan subset "dunia".

Rentetan a daripada perkataan1 ialah universal jika bagi setiap rentetan b dalam perkataan2, b ialah subset a.

Kembalikan tatasusunan semua rentetan universal dalam perkataan1. Anda boleh mengembalikan jawapan dalam sebarang pesanan.

Contoh 1:

• Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
• Output: ["facebook","google","leetcode"]

Contoh 2:

• Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
• Output: ["apple","google","leetcode"]

Kekangan:

• 1 4
• 1
• perkataan1[i] dan perkataan2[i] hanya terdiri daripada huruf kecil Inggeris.
• Semua rentetan perkataan1 adalah unik.

Penyelesaian:

Kita perlu mengenal pasti perkataan dalam perkataan1 yang "sejagat", bermakna setiap rentetan dalam perkataan2 ialah subset perkataan daripada perkataan1.

Pendekatan:

1. Kira Kekerapan Aksara dalam perkataan2:

   • Pertama, kita perlu menentukan kiraan maksimum bagi setiap aksara merentas semua rentetan dalam perkataan2. Ini memberikan kita bilangan kejadian yang diperlukan untuk setiap aksara menjadi subset.

2. Semak Setiap Perkataan dalam perkataan1:

   • Untuk setiap perkataan dalam perkataan1, kira kekerapan setiap aksara.
   • Jika bilangan watak dalam perkataan daripada perkataan1 memenuhi atau melebihi kiraan yang diperlukan daripada perkataan2, maka perkataan itu adalah universal.

3. Kembalikan Perkataan Universal:

   • Selepas menyemak semua perkataan dalam perkataan1, kembalikan perkataan yang universal.

Mari laksanakan penyelesaian ini dalam PHP: 916. Subset Perkataan

<?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"]
?>

Penjelasan:

1. Peta Kekerapan Membina untuk perkataan2: Kami melingkari setiap perkataan dalam perkataan2 dan mengira kekerapan setiap aksara. Kami menjejaki kekerapan maksimum yang diperlukan untuk setiap aksara merentas semua perkataan dalam perkataan2.

2. Menyemak perkataan1 Perkataan: Untuk setiap perkataan dalam perkataan1, kami mengira kekerapan setiap aksara dan membandingkannya dengan kekerapan yang diperlukan daripada perkataan2. Jika perkataan itu memenuhi keperluan untuk semua watak, ia dianggap universal.

3. Hasil: Kami menyimpan semua perkataan universal dalam tatasusunan hasil dan mengembalikannya pada penghujungnya.

Kerumitan Masa:

• Membina peta kekerapan untuk perkataan2: O(n * m), dengan n ialah panjang perkataan2 dan m ialah purata panjang perkataan dalam perkataan2.
• Menyemak perkataan1: O(k * m), dengan k ialah panjang perkataan1 dan m ialah purata panjang perkataan dalam perkataan1.
• Jumlah kerumitan masa adalah lebih kurang O(n * m k * m).

Pendekatan ini memastikan kami menyemak setiap perkataan dengan cekap dan memenuhi kekangan masalah.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci . Subset Perkataan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!