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 算法。

以上是JavaScript 程序检查字符串是否相互旋转的详细内容。更多信息请关注PHP中文网其他相关文章！