Program JavaScript menyemak sama ada rentetan diputar secara relatif antara satu sama lain

Putaran rentetan antara satu sama lain bermakna dua rentetan boleh diputar ke kanan atau kiri untuk mendapatkan rentetan lain. Dalam aksara rentetan yang diputar ke kanan, beralih ke indeksnya yang seterusnya, dan untuk indeks sifar, dengan mengandaikan rentetan itu berada dalam bulatan, ambil watak indeks terakhir. Putaran kiri adalah serupa dengan putaran kanan, tetapi dalam arah yang bertentangan. Kami akan diberikan dua rentetan dan kita perlu menentukan sama ada kita boleh mendapatkan rentetan yang lain dengan memutarkan aksara satu rentetan.

Masuk

string1: “abcdef” 
string2: “cdefab”

Output

Yes

Penjelasan: Kita boleh memutarkan rentetan pertama ke kiri dua kali untuk mendapatkan rentetan kedua. String1 selepas gelung pertama akan menjadi "bcdefa" dan pada gelung seterusnya ia akan sama dengan rentetan kedua.

Masuk

String1: “abcdef”
String2: “bcadef” 

Output

No

Penjelasan - Bilangan maksimum putaran yang boleh kita putar rentetan atau tatasusunan tanpa mendapat rentetan asal adalah sama dengan panjang rentetan atau tatasusunan yang diberikan.

Di sini, selepas enam putaran, kita tidak boleh mendapatkan rentetan 2 daripada rentetan 1, membuktikan bahawa tidak mungkin untuk menjadikan dua rentetan sama selepas bilangan putaran maksimum.

Kaedah naif

Dalam kaedah ini kita hanya memutarkan rentetan yang diberikan mengikut bilangan kali panjangnya dan memadankannya dengan rentetan lain yang diberikan.

Contoh

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

Output

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.

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N*N), dengan N ialah saiz rentetan yang diberikan.

Kerumitan ruang kod di atas ialah O(1) kerana kami tidak menggunakan sebarang ruang.

Algoritma KMP

Dalam program ini kita akan menggunakan algoritma KMP untuk mencari putaran, mari kita beralih kepada kod.

Contoh

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

Output

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.

Kerumitan masa dan ruang

Untuk program di atas, kerumitan masa dan ruang adalah O(N). Kami menggunakan ruang tambahan untuk menyimpan nilai dalam tatasusunan lps.

Kesimpulan

Dalam tutorial ini, kami melaksanakan program JavaScript untuk menyemak sama ada rentetan yang diberikan boleh diperoleh daripada rentetan lain yang diberikan dengan memutar aksara rentetan ke kiri atau kanan. Kami menggunakan pendekatan naif, yang mengambil kerumitan masa O(N*N) dan kerumitan ruang O(1). Selain itu, kami melaksanakan algoritma KMP dengan kerumitan masa dan ruang O(N).

Atas ialah kandungan terperinci Program JavaScript menyemak sama ada rentetan diputar secara relatif antara satu sama lain. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!