Le programme JavaScript vérifie si les chaînes pivotent les unes par rapport aux autres

La rotation des cordes entre elles signifie que deux cordes peuvent être tournées à droite ou à gauche pour obtenir une autre corde. Dans un caractère tourné à droite d'une chaîne, passez à son index suivant, et pour le zéroième index, en supposant que la chaîne est dans un cercle, prenez le caractère du dernier index. La rotation à gauche est similaire à la rotation à droite, mais dans le sens opposé. Nous recevrons deux chaînes et nous devons déterminer si nous pouvons obtenir l'autre chaîne en faisant tourner les caractères d'une chaîne.

Entrez

string1: “abcdef” 
string2: “cdefab”

Sortie

Yes

Explication : Nous pouvons faire pivoter la première chaîne vers la gauche deux fois pour obtenir la deuxième chaîne. String1 après la première boucle sera "bcdefa" et lors de la boucle suivante, ce sera le même que la deuxième chaîne.

Entrez

String1: “abcdef”
String2: “bcadef” 

Sortie

No

Explication - Le nombre maximum de rotations dont nous pouvons faire pivoter une chaîne ou un tableau sans obtenir la chaîne d'origine est égal à la longueur de la chaîne ou du tableau donné.

Ici, après six rotations, nous ne pouvons pas obtenir la chaîne 2 à partir de la chaîne 1, prouvant qu'il n'est pas possible de rendre deux chaînes égales après le nombre maximum de rotations.

Méthode naïve

Dans cette méthode, nous faisons simplement pivoter la chaîne donnée de sa longueur plusieurs fois et la faisons correspondre avec une autre chaîne donnée.

Exemple

// 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.");
}

Sortie

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.

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N*N), où N est la taille de la chaîne donnée.

La complexité spatiale du code ci-dessus est O(1) car nous n'utilisons aucun espace.

Algorithme KMP

Dans ce programme nous utiliserons l'algorithme KMP pour trouver les rotations, passons au code.

Exemple

// 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.");
}

Sortie

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.

Complexité temporelle et spatiale

Pour le programme ci-dessus, la complexité temporelle et spatiale est toutes deux O(N). Nous utilisons de l'espace supplémentaire pour stocker les valeurs dans le tableau lps.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme JavaScript pour vérifier si une chaîne donnée peut être obtenue à partir d'une autre chaîne donnée en faisant pivoter les caractères de la chaîne vers la gauche ou la droite. Nous avons utilisé l’approche naïve, qui prenait en compte la complexité temporelle O(N*N) et la complexité spatiale O(1). De plus, nous avons implémenté l’algorithme KMP avec une complexité temporelle et spatiale O(N).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!