Zählen Sie die Anzahl der konsistenten Zeichenfolgen

1684. Zählen Sie die Anzahl der konsistenten Zeichenfolgen

Schwierigkeit:Einfach

Themen:Array, Hash-Tabelle, String, Bitmanipulation, Zählen

Sie erhalten eine zulässige Zeichenfolge, die aus unterschiedlichen Zeichen und einer Reihe von Zeichenfolgenwörtern besteht. Eine Zeichenfolge ist konsistent, wenn alle Zeichen in der Zeichenfolge in der zulässigen Zeichenfolge vorkommen.

Gibt die Anzahl der konsistenten Zeichenfolgen in den Array-Wörtern zurück.

Beispiel 1:

• Eingabe: erlaubt = „ab“, Wörter = [„ad“, „bd“, „aaab“, „baa“, „badab“]
• Ausgabe: 2
• Erklärung: Die Zeichenfolgen „aaab“ und „baa“ sind konsistent, da sie nur die Zeichen „a“ und „b“ enthalten.

Beispiel 2:

• Eingabe: erlaubt = „abc“, Wörter = [„a“, „b“, „c“, „ab“, „ac“, „bc“, „abc“]
• Ausgabe: 7
• Erklärung:Alle Zeichenfolgen sind konsistent.

Beispiel 3:

• Eingabe: erlaubt = "cad", Wörter = ["cc", "acd", "b", "ba", "bac", "bad", "ac", "d"]
• Ausgabe: 4
• Erklärung: Die Zeichenfolgen „cc“, „acd“, „ac“ und „d“ sind konsistent.

Einschränkungen:

• 1 <= Wörter.Länge <= 10⁴
• 1 <= erlaubte Länge <= 26
• 1 <= Wörter[i].Länge <= 10
• Die zulässigen Zeichen sind eindeutig.
• Wörter[i] und erlaubt enthalten nur englische Kleinbuchstaben.

Hinweis:

1. Eine Zeichenfolge ist falsch, wenn sie ein unzulässiges Zeichen enthält
2. Einschränkungen sind klein genug für rohe Gewalt

Lösung:

Die Idee besteht darin, zu überprüfen, ob jedes Wort im Wortarray konsistent mit den Zeichen in der zulässigen Zeichenfolge ist. Ein Wort ist konsistent, wenn alle seine Zeichen in der zulässigen Zeichenfolge vorhanden sind.

Planen

1. Zulässiger Zeichensatz:

   • Wir können die zulässige Zeichenfolge in einen Zeichensatz umwandeln, um effizient zu prüfen, ob jedes Zeichen im Wort im Satz vorhanden ist.

2. Wortkonsistenzprüfung:

   • Überprüfen Sie für jedes Wort im Wortarray, ob alle seine Zeichen im zulässigen Satz vorhanden sind.

3. Konsistente Wörter zählen:

   • Initialisieren Sie einen Zähler. Erhöhen Sie den Zähler für jedes Wort, das konsistent ist.

4. Zählung zurückgeben:

   • Sobald alle Wörter verarbeitet wurden, wird die Anzahl der konsistenten Wörter zurückgegeben.

Lassen Sie uns diese Lösung in PHP implementieren: 1684. Zählen Sie die Anzahl der konsistenten Zeichenfolgen

<?php
/**
 * @param String $allowed
 * @param String[] $words
 * @return Integer
 */
function countConsistentStrings($allowed, $words) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:

// Example 1:
$allowed = "ab";
$words = ["ad", "bd", "aaab", "baa", "badab"];
echo countConsistentStrings($allowed, $words); // Output: 2

// Example 2:
$allowed = "abc";
$words = ["a","b","c","ab","ac","bc","abc"];
echo countConsistentStrings($allowed, $words); // Output: 7

// Example 3:
$allowed = "cad";
$words =  ["cc","acd","b","ba","bac","bad","ac","d"];
echo countConsistentStrings($allowed, $words); // Output: 4
?>




<h3>
  
  
  Erläuterung:
</h3>

<ol>
<li>
<p><strong>Zulässiger Satz</strong>:</p>

<ul>
<li>Wir erstellen ein assoziatives Array $allowedSet, in dem jeder Schlüssel ein Zeichen aus der zulässigen Zeichenfolge ist. Dies ermöglicht schnelle Suchvorgänge.</li>
</ul>
</li>
<li>
<p><strong>Wortkonsistenz</strong>:</p>

<ul>
<li>Für jedes Wort im Wortarray durchlaufen wir seine Zeichen und prüfen, ob sie in $allowedSet enthalten sind. Wenn wir ein Zeichen finden, das nicht in der Menge enthalten ist, wird das Wort als inkonsistent markiert und wir fahren mit dem nächsten Wort fort.</li>
</ul>
</li>
<li>
<p><strong>Zählen</strong>:</p>

<ul>
<li>Jedes Mal, wenn wir ein konsistentes Wort finden, erhöhen wir den Zähler $consistentCount.</li>
</ul>
</li>
<li>
<p><strong>Ergebnis zurückgeben</strong>:</p>

<ul>
<li>Nachdem alle Wörter verarbeitet wurden, enthält der Zähler die Anzahl der konsistenten Zeichenfolgen, die wir zurückgeben.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Zeitkomplexität:
</h3>

<ul>
<li>
<strong>Zeitkomplexität</strong>: O(n * m), wobei n die Anzahl der Wörter und m die durchschnittliche Länge der Wörter ist. Wir gehen alle Wörter und ihre Zeichen durch.</li>
</ul>

<h3>
  
  
  Beispielhafte Vorgehensweise:
</h3>

<p>Zur Eingabe:<br>
</p>

<pre class="brush:php;toolbar:false">$allowed = "ab";
$words = ["ad", "bd", "aaab", "baa", "badab"];

• Wir erstellen einen Satz: erlaubtSet = ['a' => wahr, 'b' => wahr].
• Überprüfen Sie jedes Wort:
  • „ad“ ist inkonsistent (enthält „d“).
  • „bd“ ist inkonsistent (enthält „d“).
  • „aaab“ ist konsistent (enthält nur „a“ und „b“).
  • „baa“ ist konsistent (enthält nur „a“ und „b“).
  • „badab“ ist inkonsistent (enthält „d“).

Die Funktion gibt also 2 zurück.

Pengendalian Kekangan:

• Memandangkan dibenarkan hanya boleh mempunyai sehingga 26 aksara berbeza dan perkataan mempunyai paling banyak 10,000 entri, penyelesaian kekerasan ini cukup cekap memandangkan kekangan. Setiap perkataan boleh mempunyai panjang maksimum 10, menjadikannya boleh diulang ke atas semua aksara.

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

Das obige ist der detaillierte Inhalt vonZählen Sie die Anzahl der konsistenten Zeichenfolgen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!