JavaScript程序：检查字符串是否互为旋转字符串

---

字符串互为旋转字符串意味着两个字符串可以通过向右或向左旋转得到另一个字符串。向右旋转时，字符串的字符移到其下一个索引，而对于第零个索引，它取最后一个索引的字符（假设字符串是一个环）。左旋转类似于右旋转，但方向相反。我们将得到两个字符串，我们必须找到是否可以通过旋转字符串的字符来得到另一个字符串。

输入

string1: “abcdef” 
string2: “cdefab”

输出

Yes

解释：我们可以将第一个字符串向左旋转两次得到第二个字符串。第一次旋转后，String1 将变为“bcdefa”，第二次旋转后，它将与第二个字符串相同。

输入

String1: “abcdef”
String2: “bcadef” 

输出

No

解释 - 我们可以旋转一个字符串或数组的最大旋转次数（而不得到原始字符串）等于给定字符串或数组的长度。

这里，在六次旋转后，我们无法从字符串1得到字符串2，证明不可能在最大旋转次数后使两个字符串相等。

朴素方法

在这种方法中，我们将只旋转给定字符串的长度次数，并与另一个给定字符串匹配。

示例

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

输出

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.

时间和空间复杂度

上述代码的时间复杂度为 O(N*N)，其中 N 是给定字符串的大小。

上述代码的空间复杂度为 O(1)，因为我们没有使用任何空间。

KMP算法

在这个程序中，我们将使用 KMP 算法来查找旋转，让我们来看代码。

示例

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

输出

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.

时间和空间复杂度

对于上述程序，时间和空间复杂度均为 O(N)。我们使用了额外的空间来存储 lps 数组中的值。

结论

在本教程中，我们实现了一个 JavaScript 程序来检查我们是否可以通过向左或向右旋转字符串的字符来从另一个给定字符串获得一个给定字符串。我们使用了朴素方法，其时间复杂度为 O(N*N)，空间复杂度为 O(1)。此外，我们还实现了具有 O(N) 时间和空间复杂度的 KMP 算法。