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中文網其他相關文章！