Python-Programm: Finden Sie die Mindestanzahl an Umdrehungen, die erforderlich sind, um die tatsächliche Zeichenfolge zu erhalten?

Zu verstehen, wie man Strings effizient verarbeitet, ist eine grundlegende Programmieraufgabe, die die Leistung Ihres Codes erheblich verbessern kann. Eine interessante Herausforderung bei der Saitenmanipulation besteht darin, die Mindestanzahl an Drehungen zu ermitteln, die erforderlich ist, um aus einer gedrehten Saite die gewünschte Saite zu erzeugen. Dieses Problem tritt häufig in Situationen wie Textverarbeitung, Kryptografie und Datenkomprimierung auf.

Stellen Sie sich den Fall vor, dass eine Saite um einen bestimmten Betrag nach rechts gedreht wird. Das Ziel besteht darin, die minimale Anzahl an Umdrehungen zu ermitteln, die erforderlich sind, um die Saite wieder in ihre ursprüngliche Form umzuwandeln. Indem wir die Lösung für dieses Problem finden, können wir mehr über die String-Struktur erfahren und nützliche Informationen erhalten.

In diesem Artikel werden zwei Methoden zur Bestimmung der Mindestanzahl an Drehungen beschrieben, die erforderlich sind, um aus einer gedrehten Saite die ursprüngliche Saite wiederherzustellen. Zur Umsetzung dieser Technologien in die Praxis wird Python verwendet, eine flexible und beliebte Programmiersprache, die für ihre Lesbarkeit und Benutzerfreundlichkeit bekannt ist.

Methode

Um in Python zu suchen, um die Mindestanzahl an Drehungen einer tatsächlichen Zeichenfolge zu ermitteln, können wir zwei Methoden anwenden –

• Wenden Sie rohe Gewalt an.

• Verwenden Sie While-Schleifen in benutzerdefinierten Funktionen.

Lassen Sie uns diese beiden Methoden untersuchen -

Methode 1: Brutale Gewalt anwenden

Verwenden Sie die Brute-Force-Methode, um die erste Saite in alle möglichen Positionen zu drehen und vergleichen Sie dann die zweite Saite mit der gedrehten ersten Saite. Wir verfolgen die Mindestanzahl an Umdrehungen, die erforderlich sind, um die zweite Zeichenfolge zu erhalten, indem wir alle möglichen Umdrehungen durchlaufen. Wenn nach Ende der Schleife die minimale Rotationsvariable immer noch unendlich ist, ist es unmöglich, die zweite Zeichenfolge durch Drehen der ersten Zeichenfolge zu erhalten. Wenn nicht, geben wir die erforderliche Mindestanzahl an Spins zurück. Die zeitliche Komplexität dieser Methode beträgt O(n^2), wobei n die Länge der ersten Zeichenfolge ist.

Algorithmus

Die Schritte zum Suchen nach der Mindestanzahl an Drehungen in Python, um die tatsächliche Zeichenfolge zu erhalten, sind wie folgt -

Schritt 1 – Erstellen Sie eine Funktion, die zwei Zeichenfolgen als Eingabe akzeptiert.

Schritt 2 – Erstellen Sie eine Variable mit einem Anfangswert von unendlich, um die Mindestanzahl der erforderlichen Drehungen im Auge zu behalten.

Schritt 3 – Durchlaufen Sie die möglichen Werte von 0 bis zur Länge der ersten Zeichenfolge.

Schritt 4- Die erste Saite sollte um die aktuelle Indexposition gedreht werden. Dadurch wird überprüft, ob die zweite Zeichenfolge und die gedrehte Zeichenfolge gleich sind. Wenn ja, ändern Sie den Wert der Variablen auf den Mindestwert zwischen dem aktuellen Mindestwert und dem aktuellen Index.

Schritt 5− Wenn die minimale Rotationsvariable immer noch auf unendlich eingestellt ist, geben Sie -1 zurück (was anzeigt, dass es nicht möglich ist, die zweite Zeichenfolge durch Drehen der ersten Zeichenfolge abzurufen).

Schritt 6 – Wenn keine vorhanden ist, geben Sie die Variable für die minimale Rotation zurück.

Beispiel

def min_rotations_bf(s1, s2):
   min_rotations = float('inf')

   for i in range(len(s1)):
      rotated = s1[i:] + s1[:i]
      if rotated == s2:
         min_rotations = min(min_rotations, i)

   if min_rotations == float('inf'):
      return -1
   else:
      return min_rotations


# Example usage
s1 = "program"
s2 = "grampro"
bf_result = min_rotations_bf(s1, s2)

print("String 1:", s1)
print("String 2:", s2)
print("Minimum rotations (Brute Force):", bf_result)

Ausgabe

String 1: program
String 2: grampro
Minimum rotations (Brute Force): 3

Methode 2: Verwenden einer While-Schleife in einer benutzerdefinierten Funktion

Was funktioniert, ist die Verwendung der verketteten Zeichenfolge, um zu überprüfen, ob die zweite Zeichenfolge vorhanden ist, anstatt eine explizite Zeichenfolgenrotation durchzuführen. Wenn der zweite String nicht durch Rotation des ersten Strings abgerufen werden kann, weil die beiden Strings unterschiedlich lang sind, geben wir -1 zurück. Indem wir feststellen, ob die zweite Zeichenfolge eine Teilzeichenfolge der verketteten Zeichenfolge ist, können wir herausfinden, wie viele Umdrehungen erforderlich sind, um die zweite Zeichenfolge von der ersten zu trennen. Um die Mindestanzahl an Umdrehungen zu bestimmen, berechnen wir den Index und dividieren ihn durch die Länge des ersten Strings, wenn der zweite String als Teilstring gefunden wird. Die zeitliche Komplexität dieser Methode beträgt O(n), wobei n die Länge der ersten Zeichenfolge ist.

Algorithmus

Die Schritte zum Suchen nach der Mindestanzahl an Drehungen in Python, um die tatsächliche Zeichenfolge zu erhalten, sind wie folgt -

Schritt 1 – Erstellen Sie eine Funktion, die zwei Zeichenfolgen als Eingabe akzeptiert.

Schritt 2- Wenn die Längen der beiden Zeichenfolgen nicht gleich sind, geben Sie -1 zurück (da die zweite Zeichenfolge nicht durch Drehen der ersten Zeichenfolge erhalten werden kann).

Schritt 3 – Erstellen Sie eine temporäre Zeichenfolge, indem Sie die erste Zeichenfolge mit sich selbst verketten.

Schritt 4 – Wenn die zweite Zeichenfolge eine Teilzeichenfolge der temporären Zeichenfolge ist, geben Sie die erforderliche Mindestanzahl an Umdrehungen als Index der zweiten Zeichenfolge in der temporären Zeichenfolge dividiert durch die Länge der ersten Zeichenfolge zurück.

Schritt 5− Wenn nicht, geben Sie -1 zurück.

Beispiel

def min_rotations_efficient(s1, s2):
   if len(s1) != len(s2):
      return -1

   rotations = 0
   n = len(s1)

   # Check for left rotations
   while rotations < n:
      if s1 == s2:
         return rotations
      s1 = s1[1:] + s1[0]
      rotations += 1

   # Check for right rotations
   s1 = s1[-1] + s1[:-1]
   rotations = 1

   while rotations <= n:
      if s1 == s2:
         return rotations
      s1 = s1[-1] + s1[:-1]
      rotations += 1

   return -1
# Example usage
s1 = "program"
s2 = "grampro"
efficient_result = min_rotations_efficient(s1, s2)

print("String 1:", s1)
print("String 2:", s2)
print("Minimum rotations ", efficient_result)

Ausgabe

String 1: program
String 2: grampro
Minimum rotations  3

Fazit

In diesem Artikel haben wir uns zwei Methoden zur Berechnung der Mindestanzahl an Umdrehungen angesehen, die erforderlich sind, um eine bestimmte Saite in eine andere Saite umzuwandeln. Die zweite Methode verwendet die verketteten Zeichenfolgen, um zu prüfen, ob die zweite Zeichenfolge existiert, während die Brute-Force-Methode die erste Zeichenfolge um jede mögliche Anzahl von Positionen dreht. Abhängig von der Größe der Eingabe und der erforderlichen Effizienz kann man die beste Strategie zur Lösung dieses Problems in Python wählen. Dank dieser Methoden können Sie nun die Mindestanzahl an Umdrehungen berechnen, die erforderlich sind, um eine Zielschnur aus einer bestimmten Schnur zu extrahieren.

Das obige ist der detaillierte Inhalt vonPython-Programm: Finden Sie die Mindestanzahl an Umdrehungen, die erforderlich sind, um die tatsächliche Zeichenfolge zu erhalten?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!