Wie kann man effizient feststellen, ob zwei Saiten Drehungen voneinander sind?

Überprüfung der String-Rotation: Eine effiziente Lösung

In einem Vorstellungsgespräch für eine Stelle als Softwareentwickler wurde ein Kandidat vor die Herausforderung gestellt: Bestimmen Sie, ob zwei vorhanden sind Zeichenfolgen sind gedrehte Versionen voneinander. Konkret bestand die Aufgabe darin, anhand von „s1“ und „s2“ zu überprüfen, ob „s1“ eine modifizierte Version von „s2“ ist, indem die Zeichen rotiert werden.

Der Ansatz des Interviewers

Die Antwort des Kandidaten bestand darin, das längste Präfix in „s2“ zu finden, das mit einem Teilstring in „s1“ übereinstimmte, der den Rotationspunkt darstellen würde. Durch die Aufteilung von „s2“ an diesem Punkt in „s2a“ und „s2b“ könnte die Verkettung von „s2a“ und „s2b“ hinsichtlich der Gleichheit mit „s1“ verglichen werden.

Eine einfachere Lösung

Der Interviewer schlug jedoch einen direkteren Ansatz vor: Stellen Sie sicher, dass „s1“ und „s2“ die gleiche Länge haben, und testen Sie dann, ob „s2“ ein mit sich selbst verketteter Teilstring von „s1“ ist. Diese Methode nutzt die Tatsache aus, dass eine gedrehte Zeichenfolge immer eine Teilzeichenfolge der ursprünglichen Zeichenfolge ist, wenn sie mit ihr verkettet wird.

Java-Implementierung

In Java eine einfache Implementierung von Diese Lösung könnte wie folgt aussehen:

<code class="java">boolean isRotation(String s1, String s2) {
    return (s1.length() == s2.length()) && ((s1 + s1).indexOf(s2) != -1);
}</code>

Effizienzanalyse

Die Zeitkomplexität dieser Lösung beträgt O(n), wobei n die Länge der Zeichenfolgen ist, da sie umfasst eine einzelne Zeichenfolgenverkettung und eine Teilzeichenfolgensuche für das kombinierte Ergebnis. Aufgrund des Platzbedarfs für die verkettete Zeichenfolge beträgt auch die Raumkomplexität O(n).

Durch die Bereitstellung einer unkomplizierten und effizienten Methode zur Überprüfung der Zeichenfolgenrotation erfüllt dieser alternative Ansatz den Wunsch des Interviewers nach Einfachheit und Effektivität erkennt gedrehte Versionen von Strings.

Das obige ist der detaillierte Inhalt vonWie kann man effizient feststellen, ob zwei Saiten Drehungen voneinander sind?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!