Das JavaScript-Programm prüft, ob Zeichenfolgen relativ zueinander gedreht sind

Saitenrotation untereinander bedeutet, dass zwei Saiten nach rechts oder links gedreht werden können, um eine andere Saite zu erhalten. Wechseln Sie bei einem nach rechts gedrehten Zeichen einer Zeichenfolge zum nächsten Index und nehmen Sie für den nullten Index, vorausgesetzt, die Zeichenfolge befindet sich in einem Kreis, das Zeichen des letzten Index. Die Linksdrehung ähnelt der Rechtsdrehung, jedoch in entgegengesetzter Richtung. Wir erhalten zwei Zeichenfolgen und müssen feststellen, ob wir die andere Zeichenfolge erhalten können, indem wir die Zeichen einer Zeichenfolge rotieren.

Eintreten

string1: “abcdef” 
string2: “cdefab”

Ausgabe

Yes

Erklärung: Wir können die erste Saite zweimal nach links drehen, um die zweite Saite zu erhalten. String1 nach der ersten Schleife lautet „bcdefa“ und in der nächsten Schleife ist er derselbe wie der zweite String.

Eintreten

String1: “abcdef”
String2: “bcadef” 

Ausgabe

No

Erklärung – Die maximale Anzahl an Drehungen, die wir einen String oder ein Array drehen können, ohne den ursprünglichen String zu erhalten, ist gleich der Länge des gegebenen Strings oder Arrays.

Hier können wir nach sechs Umdrehungen String 2 nicht von String 1 erhalten, was beweist, dass es nicht möglich ist, zwei Strings nach der maximalen Anzahl von Umdrehungen gleich zu machen.

Naive Methode

Bei dieser Methode drehen wir einfach die gegebene Zeichenfolge mehrmals um ihre Länge und gleichen sie mit einer anderen gegebenen Zeichenfolge ab.

Beispiel

// function to rotate the string in the left direction 
function left_rotate(str){

   // splitting the string and then again joining back 
   str = str.substr(1) + str.substr(0,1);
   return str;
}

// function to check if one string is equal to another after certain rotations
function check(str1, str2){

   // checking the size of both strings 
   if(str1.length != str2.length){
      return false;
   } 
   var k = str1.length
   while(k--){
      if(str1 == str2){
         return true;
      }
      str1 = left_rotate(str1);
   }
   return false;
}

// defining the strings
var str1 = "abcdef" 
var str2 = "cdefab"
console.log("The given strings are " + str1 + " and " + str2);

// calling the function 
if(check(str1,str2)){
   console.log("Yes, we can obtain the second string from the given string by rotating it.");
} else{
   console.log("No, we cannot obtain the second string from the given string by rotating it.");
}

// defining the strings
str1 = "abcdef" 
str2 = "bacdef"
console.log("The given strings are " + str1 + " and " + str2);

// calling the function 
if(check(str1,str2)){
   console.log("Yes, we can obtain the second string from the given string by rotating it.");
} else{
   console.log("No, we cannot obtain the second string from the given string by rotating it.");
}

Ausgabe

The given strings are abcdef and cdefab
Yes, we can obtain the second string from the given string by rotating it.
The given strings are abcdef and bacdef
No, we cannot obtain the second string from the given string by rotating it.

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N*N), wobei N die Größe der angegebenen Zeichenfolge ist.

Die Raumkomplexität des obigen Codes beträgt O(1), da wir keinen Raum verwenden.

KMP-Algorithmus

In diesem Programm verwenden wir den KMP-Algorithmus, um Rotationen zu finden. Kommen wir zum Code.

Beispiel

// function to check if one string is equal to another using KMP
function check(str1, str2){

   // checking the size of both strings 
   if(str1.length != str2.length){
      return false;
   } 
   var len = str1.length;
   
   // create lps that will hold the longest prefix
   var lps = Array.from({length: len}, (_, i) => 0);
   
   // length of the previous longest prefix suffix
   var len_p = 0;
   var i = 1;
   lps[0] = 0; 
   
   // the loop calculates lps[i] for i = 1 to n-1
   while (i < len) {
      if (str1.charAt(i) == str2.charAt(len_p)) {
         lps[i] = ++len_p;
         i++;
      } else {
         if (len_p == 0) {
            lps[i] = 0;
            i++;
         } else {
            len_p = lps[len_p - 1];
         }
      }
   }
   i = 0;
   
   // match from that rotating point
   for(var k = lps[len - 1]; k < len; k++) {
      if (str2.charAt(k) != str1.charAt(i++)){
         return false;
      }
   }
   return true;
}

// defining the strings
var str1 = "abcdef" 
var str2 = "cdefab"
console.log("The given strings are " + str1 + " and " + str2);

// calling the function 
if(check(str1,str2)){
   console.log("Yes, we can obtain the second string from the given string by rotating it.");
} else{
   console.log("No, we cannot obtain the second string from the given string by rotating it.");
}

// defining the strings
str1 = "abcdef" 
str2 = "bacdef"
console.log("The given strings are " + str1 + " and " + str2);

// calling the function 
if(check(str1,str2)){
   console.log("Yes, we can obtain the second string from the given string by rotating it.");
} else{
   console.log("No, we cannot obtain the second string from the given string by rotating it.");
}

Ausgabe

The given strings are abcdef and cdefab
Yes, we can obtain the second string from the given string by rotating it.
The given strings are abcdef and bacdef
No, we cannot obtain the second string from the given string by rotating it.

Zeitliche und räumliche Komplexität

Für das obige Programm sind sowohl die Zeit- als auch die Raumkomplexität O(N). Wir verwenden zusätzlichen Speicherplatz, um die Werte im LPS-Array zu speichern.

Fazit

In diesem Tutorial haben wir ein JavaScript-Programm implementiert, um zu prüfen, ob eine bestimmte Zeichenfolge aus einer anderen bestimmten Zeichenfolge erhalten werden kann, indem die Zeichen der Zeichenfolge nach links oder rechts gedreht werden. Wir verwendeten den naiven Ansatz, der O(N*N) Zeitkomplexität und O(1) Raumkomplexität benötigte. Zusätzlich haben wir den KMP-Algorithmus mit O(N) Zeit- und Raumkomplexität implementiert.

Das obige ist der detaillierte Inhalt vonDas JavaScript-Programm prüft, ob Zeichenfolgen relativ zueinander gedreht sind. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!