String-Matching in einem Array

1408. String-Matching in einem Array

Schwierigkeit:Einfach

Themen:Array, String, String-Matching

Gibt bei einem gegebenen Array von Zeichenfolgenwörtern alle Zeichenfolgen in Wörtern zurück, die eine Teilzeichenfolge eines anderen Wortes sind. Sie können die Antwort in beliebiger Reihenfolge zurücksenden.

Ein Teilstring ist eine zusammenhängende Folge von Zeichen innerhalb eines Strings

Beispiel 1:

• Eingabe: Wörter = ["Masse", "als", "Held", "Superheld"]
• Ausgabe: ["as","hero"]
• Erklärung: „as“ ist ein Teilstring von „mass“ und „hero“ ist ein Teilstring von „superhero“. [„hero“, „as“] ist auch eine gültige Antwort.

Beispiel 2:

• Eingabe:words = ["leetcode","et","code"]
• Ausgabe: ["et","code"]
• Erklärung: „et“, „code“ sind Teilzeichenfolgen von „leetcode“.

Beispiel 3:

• Eingabe: Wörter = ["blau", "grün", "bu"]
• Ausgabe: []
• Erklärung: Keine Wortfolge ist Teilzeichenfolge einer anderen Zeichenfolge.

Einschränkungen:

• 1
• 1
• Wörter[i] enthält nur englische Kleinbuchstaben.
• Alle Wortketten sind einzigartig.

Hinweis:

1. Bruteforce, um herauszufinden, ob eine Zeichenfolge Teilzeichenfolge einer anderen ist, oder KMP-Algorithmus verwenden.

Lösung:

Wir müssen alle Zeichenfolgen im Wortarray finden, die Teilzeichenfolgen eines anderen Wortes im Array sind. Sie können einen Brute-Force-Ansatz verwenden. Der Ansatz besteht darin, jede Zeichenfolge in der Liste zu überprüfen und zu überprüfen, ob es sich um eine Teilzeichenfolge einer anderen Zeichenfolge handelt.

Lassen Sie uns diese Lösung in PHP implementieren: 1408. String-Matching in einem Array

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

// Example 1
$words = ["mass", "as", "hero", "superhero"];
print_r(stringMatching($words));

// Example 2
$words = ["leetcode", "et", "code"];
print_r(stringMatching($words));

// Example 3
$words = ["blue", "green", "bu"];
print_r(stringMatching($words));
?>

Erläuterung:

1. Die Funktion stringMatching durchläuft alle Wörter im Eingabearray.
2. Für jedes Wort wird es mithilfe einer verschachtelten Schleife mit jedem anderen Wort im Array verglichen.
3. Es verwendet die Funktion strpos() von PHP, um zu überprüfen, ob eine Zeichenfolge eine Teilzeichenfolge einer anderen ist. Die Funktion strpos() gibt false zurück, wenn der Teilstring nicht gefunden wird.
4. Wenn eine Teilzeichenfolge gefunden wird, fügen wir das Wort zum Ergebnisarray hinzu und verlassen die innere Schleife, da wir das Wort nur einmal aufzeichnen müssen.
5. Schließlich gibt die Funktion das Ergebnisarray zurück, das alle Teilzeichenfolgen enthält.

Zeitkomplexität:

• Die Zeitkomplexität beträgt O(n² x m), wobei n die Anzahl von ist Wörter und m ist die maximale Länge eines Wortes. Dies liegt daran, dass wir für jedes Wort in jedem anderen Wort eine Teilzeichenfolgensuche durchführen.

Beispielausgaben:

Für die Eingabe ["mass", "as", "hero", "superhero"] lautet die Ausgabe:

Array
(
    [0] => as
    [1] => hero
)

Für die Eingabe ["leetcode", "et", "code"] lautet die Ausgabe:

Array
(
    [0] => et
    [1] => code
)

Für die Eingabe ["blau", "grün", "bu"] lautet die Ausgabe:

Array
(
)

Diese Lösung eignet sich gut für die gegebenen Problembeschränkungen.

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 vonString-Matching in einem Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!