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.
string1: “abcdef” string2: “cdefab”
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.
String1: “abcdef” String2: “bcadef”
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.
In this method we just rotate the given string its length number of times and match it with another given string.
// 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.
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.
In this program we will use the KMP algorithm to find rotations, let's move to the code.
// 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.
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 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!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
