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

字符串互为旋转是指两个字符串可以通过向右或向左旋转得到另一个字符串。在向右旋转中，字符串中的字符向后移动一个索引，对于零索引，它将取最后一个索引的字符，假设字符串是一个圆。左旋转与右旋转类似，但方向相反。我们将得到两个字符串，并要求通过旋转字符串的字符来判断是否能够得到另一个字符串。

输入

string1: “abcdef” 
string2: “cdefab”

输出

Yes

说明：我们可以将第一个字符串向左旋转两次，得到第二个字符串。字符串1在第一次旋转后变为”bcdefa”，在第二次旋转后与第二个字符串相同。

输入

String1: “abcdef”
String2: “bcadef”

输出

No

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

在这个示例中，经过六次旋转，我们无法从string1得到string2，证明在最大旋转次数之后，无法使两个字符串相等。

原生方法

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

示例

// 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.