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 <= W?rter.L?nge <= 100
• 1 <= W?rter[i].L?nge <= 30
• 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));
?>




<h3>
  
  
  Erl?uterung:
</h3>

<ol>
<li>Die Funktion stringMatching durchl?uft alle W?rter im Eingabearray.</li>
<li>Für jedes Wort wird es mithilfe einer verschachtelten Schleife mit jedem anderen Wort im Array verglichen.</li>
<li>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.</li>
<li>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.</li>
<li>Schlie?lich gibt die Funktion das Ergebnisarray zurück, das alle Teilzeichenfolgen enth?lt.</li>
</ol>

<h3>
  
  
  Zeitkomplexit?t:
</h3>

<ul>
<li>Die Zeitkomplexit?t betr?gt <em><strong>O(n<sup>2</sup> x m)</strong></em>, wobei <em><strong>n</strong></em> die Anzahl von ist W?rter und <em><strong>m</strong></em> ist die maximale L?nge eines Wortes. Dies liegt daran, dass wir für jedes Wort in jedem anderen Wort eine Teilzeichenfolgensuche durchführen.</li>
</ul>

<h3>
  
  
  Beispielausgaben:
</h3>

<p>Für die Eingabe ["mass", "as", "hero", "superhero"] lautet die Ausgabe:<br>
</p>

<pre class="brush:php;toolbar:false">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!