. String drehen

796. String drehen

Schwierigkeit:Einfach

Themen:String, String-Matching

Gegeben zwei Strings s und goal, gib wahr genau dann zurück, wenn s nach einer gewissen Anzahl von Verschiebungen auf s zum Ziel werden kann.

Eine Verschiebung auf s besteht darin, das ganz linke Zeichen von s an die ganz rechte Position zu verschieben.

• Wenn beispielsweise s = „abcde“ ist, wird es nach einer Schicht „bcdea“ sein.

Beispiel 1:

• Eingabe: s = "abcde", goal = "cdeab"
• Ausgabe:wahr

Beispiel 2:

• Eingabe: s = „abcde“, goal = „abced“
• Ausgabe:false

Einschränkungen:

• 1
• s und goal bestehen aus englischen Kleinbuchstaben.

Lösung:

Wir können die Eigenschaften der String-Verkettung nutzen. Insbesondere wenn wir die Zeichenfolge s mit sich selbst verketten (d. h. s s), erscheinen alle möglichen Drehungen von s als Teilzeichenfolgen innerhalb dieser verketteten Zeichenfolge. Dadurch können wir einfach prüfen, ob das Ziel ein Teilstring von s s ist.

Lassen Sie uns diese Lösung in PHP implementieren: 796. String drehen

<?php /**
 * @param String $s
 * @param String $goal
 * @return Boolean
 */
function rotateString($s, $goal) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
?>

Erläuterung:

1. Längenprüfung: Wir prüfen zunächst, ob die Längen von s und Ziel gleich sind. Ist dies nicht der Fall, geben wir sofort false zurück, da es unmöglich ist, s in goal umzuwandeln.

2. Verkettung: Wir verketten die Zeichenfolge s mit sich selbst, um doubleS zu erstellen.

3. Substring-Prüfung: Wir verwenden die Funktion strpos(), um zu prüfen, ob das Ziel als Teilstring in doubleS vorhanden ist. Wenn ja, geben wir true zurück; andernfalls geben wir false zurück.

Komplexität:

• Zeitkomplexität: O(n), wobei n die Länge der Zeichenfolge aufgrund der Verkettung und Teilzeichenfolgensuche ist.
• Raumkomplexität: O(n) für die verkettete Zeichenfolge.

Diese Lösung bestimmt effizient, ob eine Saite durch Rotationen zu einer anderen werden kann.

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. String drehen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!