. Wortteilmengen

916. Wortteilmengen

Schwierigkeit:Mittel

Themen:Array, Hash-Tabelle, String

Sie erhalten zwei String-Arrays, Wörter1 und Wörter2.

Eine Zeichenfolge b ist eine Teilmenge der Zeichenfolge a, wenn jeder Buchstabe in b in a einschließlich Multiplizität vorkommt.

• Zum Beispiel ist „wrr“ eine Teilmenge von „warrior“, aber keine Teilmenge von „world“.

Eine Zeichenfolge a aus Wörter1 ist universell, wenn für jede Zeichenfolge b in Wörter2 b eine Teilmenge von a ist.

Gibt ein Array aller universellen Zeichenfolgen in Wörtern1 zurück. Sie können die Antwort in beliebiger Reihenfolge zurücksenden.

Beispiel 1:

• Eingabe: Wörter1 = ["amazon", "Apple", "Facebook", "Google", "Leetcode"], Wörter2 = ["e", "o"]
• Ausgabe: ["facebook", "google", "leetcode"]

Beispiel 2:

• Eingabe: Wörter1 = ["amazon", "Apple", "Facebook", "Google", "Leetcode"], Wörter2 = ["l", "e"]
• Ausgabe: ["Apple", "Google", "Leetcode"]

Einschränkungen:

• 1 4
• 1
• Wörter1[i] und Wörter2[i] bestehen nur aus englischen Kleinbuchstaben.
• Alle Wortfolgen1 sind einzigartig.

Lösung:

Wir müssen die Wörter in Wörter1 identifizieren, die „universell“ sind, was bedeutet, dass jede Zeichenfolge in Wörter2 eine Teilmenge des Wortes aus Wörter1 ist.

Ansatz:

1. Zählen Sie die Häufigkeit von Zeichen in Wörtern2:

   • Zuerst müssen wir die maximale Anzahl für jedes Zeichen in allen Zeichenfolgen in Wörtern bestimmen2. Dies gibt uns die erforderliche Anzahl von Vorkommen, damit jedes Zeichen eine Teilmenge darstellt.

2. Überprüfen Sie jedes Wort in Worten1:

   • Zählen Sie für jedes Wort in Wörter1 die Häufigkeit jedes Zeichens.
   • Wenn die Anzahl der Zeichen im Wort aus Wörtern 1 die erforderliche Anzahl aus Wörtern 2 erreicht oder überschreitet, ist das Wort universell.

3. Gib die universellen Worte zurück:

   • Nachdem Sie alle Wörter in Wörter1 überprüft haben, geben Sie diejenigen zurück, die universell sind.

Lassen Sie uns diese Lösung in PHP implementieren: 916. Wortteilmengen

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

Erläuterung:

1. Erstellen einer Häufigkeitskarte für Wörter2: Wir durchlaufen jedes Wort in Wörter2 und berechnen die Häufigkeit jedes Zeichens. Wir verfolgen die maximale Häufigkeit, die für jedes Zeichen in allen Wörtern in Wörtern2 benötigt wird.

2. Wörter1 Wörter prüfen: Für jedes Wort in Wörter1 berechnen wir die Häufigkeit jedes Zeichens und vergleichen sie mit der erforderlichen Häufigkeit von Wörter2. Wenn das Wort die Anforderungen für alle Zeichen erfüllt, gilt es als universell.

3. Ergebnis: Wir speichern alle universellen Wörter im Ergebnisarray und geben es am Ende zurück.

Zeitkomplexität:

• Erstellen der Häufigkeitskarte für Wörter2: O(n * m), wobei n die Länge von Wörtern2 und m die durchschnittliche Länge von Wörtern in Wörtern2 ist.
• Überprüfen von Wörtern1: O(k * m), wobei k die Länge von Wörtern1 und m die durchschnittliche Länge von Wörtern in Wörtern1 ist.
• Die Gesamtzeitkomplexität beträgt ungefähr O(n * m k * m).

Dieser Ansatz stellt sicher, dass wir jedes Wort effizient prüfen und die Einschränkungen des Problems erfüllen.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt von. Wortteilmengen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!