JavaScript program checks if strings are rotated relative to each other

String rotation means that two strings can be rotated to the right or left to obtain another string. In a right-rotated character of a string, shift to its next index, and for the zeroth index, assuming the string is in a circle, take the character of the last index. Left rotation is similar to right rotation, but in the opposite direction. We will be given two strings and we have to determine if we can get the other string by rotating the characters of one string.

enter

string1: “abcdef” 
string2: “cdefab”

Output

Yes

Explanation: We can rotate the first string to the left twice to get the second string. String1 after the first loop will be "bcdefa" and on the next loop it will be the same as the second string.

enter

String1: “abcdef”
String2: “bcadef” 

Output

No

Description - The maximum number of rotations we can rotate a string or array without getting the original string is equal to the length of the given string or array.

Here, after six rotations, we cannot get string 2 from string 1, proving that it is impossible to make two strings equal after the maximum number of rotations.

Naive method

In this method we just rotate the given string its length number of times and match it with another given string.

Example

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

Output

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.

Time and space complexity

The time complexity of the above code is O(N*N), where N is the size of the given string.

The space complexity of the above code is O(1) because we are not using any space.

KMP algorithm

In this program we will use the KMP algorithm to find rotations, let's move to the code.

Example

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

Output

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.

Time and space complexity

For the above program, the time and space complexity are both O(N). We use extra space to store the values ​​in the lps array.

in conclusion

In this tutorial, we implemented a JavaScript program to check if a given string can be obtained from another given string by rotating the characters of the string left or right. We used the naive approach, which took O(N*N) time complexity and O(1) space complexity. Additionally, we implemented the KMP algorithm with O(N) time and space complexity.

The above is the detailed content of JavaScript program checks if strings are rotated relative to each other. For more information, please follow other related articles on the PHP Chinese website!