Heim  >  Artikel  >  Web-Frontend  >  JavaScript-Programm zum Ermitteln der lexikografisch kleinsten Stringrotation

JavaScript-Programm zum Ermitteln der lexikografisch kleinsten Stringrotation

WBOY
WBOYnach vorne
2023-08-25 19:41:02973Durchsuche

JavaScript 程序查找字典顺序最小字符串旋转

Wir werden die lexikografisch kleinste Stringrotation in JavaScript finden. Die Methode beinhaltet die Verkettung der ursprünglichen Zeichenfolge mit sich selbst und die anschließende Verwendung der integrierten „Sort“-Funktion, um die verkettete Zeichenfolge in aufsteigender Reihenfolge zu sortieren. Schließlich geben wir den kleinsten Teilstring des sortierten verketteten Strings zurück, der dieselbe Länge wie der Originalstring hat. Dies ist die kleinste Stringrotation in lexikografischer Reihenfolge.

Wir werden diese Logik mithilfe von String-Manipulationstechniken und integrierten Funktionen implementieren, die in JavaScript verfügbar sind. Das Ergebnis unserer Implementierung wird eine Zeichenfolge sein, die die lexikographisch minimale Drehung der Eingabezeichenfolge darstellt. Dies ist nützlich, um Zeichenfolgen effizient zu vergleichen und zu sortieren.

In Zukunft werden wir den Algorithmus weiter verbessern, um die Suche nach der lexikographisch kleinsten Stringrotation schneller und effizienter zu machen.

Methode

Hier wird erklärt, wie man die lexikografisch kleinste Stringrotation in 5 Zeilen findet -

  • Verketten Sie die Originalzeichenfolge mit sich selbst, um sicherzustellen, dass alle möglichen Drehungen berücksichtigt werden.

  • Finden Sie das erste Zeichen, das nicht mit dem nächsten Zeichen übereinstimmt, das als Ausgangspunkt für die Mindestrotation verwendet wird.

  • Wenn kein solches Zeichen gefunden wird, wird die ursprüngliche Zeichenfolge zurückgegeben, da sie bereits minimal gedreht ist.

  • Gibt die Teilzeichenfolge in der verketteten Zeichenfolge vom gefundenen Zeichen bis zum Ende der Zeichenfolge als minimale Rotation zurück.

  • Der generierte Teilstring ist die lexikographisch kleinste Drehung des Strings.

Beispiel

Die lexikografisch kleinste Rotation einer Zeichenfolge kann ermittelt werden, indem die Originalzeichenfolge mit sich selbst verkettet wird und die kleinste Teilzeichenfolge gefunden wird, die mit dem ersten Zeichen der Originalzeichenfolge beginnt.

Hier ist ein in JavaScript implementiertes Beispiel -

function findLexicographicallyMinimumStringRotation(str) {
   let strDouble = str + str;
   let len = str.length;
   let minRotation = strDouble.substring(0, len);
   for (let i = 1; i < len; i++) {
      let currRotation = strDouble.substring(i, i + len);
      if (currRotation < minRotation) {
         minRotation = currRotation;
      }
   }
   return minRotation;
}
const str = 'eadbc';
console.log(findLexicographicallyMinimumStringRotation(str));

Anleitung

  • Zuerst verketten wir die ursprüngliche Zeichenfolge mit sich selbst, um das strDouble zu erhalten.

  • Wir definieren außerdem eine Variable len, um die Länge der Originalzeichenfolge zu speichern.

  • Dann initialisieren wir minRotation mit dem ersten Teilstring der Länge len in strDouble, also strDouble >.substring(0, len). Dies ist unser Ausgangspunkt für die Suche nach der lexikografisch kleinsten Stringrotation.

  • Wir verwenden dann eine for-Schleife, um alle möglichen Teilzeichenfolgen der Länge len in strDouble ab dem zweiten Zeichen zu durchlaufen.

  • Für jede Iteration finden wir die aktuelle Rotation currRotation , indem wir einen Teilstring der Länge len aus dem strDouble von der aktuellen Position i.

  • erhalten
  • Wenn currRotation kleiner als minRotation ist, aktualisieren wir minRotation mit der aktuellen Rotation.

  • Nachdem die for-Schleife beendet ist, geben wir schließlich den Wert von minRotation zurück, der die lexikografisch kleinste Drehung der Zeichenfolge ist.

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Ermitteln der lexikografisch kleinsten Stringrotation. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Dieser Artikel ist reproduziert unter:tutorialspoint.com. Bei Verstößen wenden Sie sich bitte an admin@php.cn löschen