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.

登錄后復制登錄后復制