Check if Two Strings are Rotations of each other
“check if two strings are rotations of each other” is a popular interview problem based on string data structure. Here, we are given two strings str1 and str2 and our task is to check whether these two strings are in rotation of each other or not.
Example:
INPUT: String 1: “abcd” String 2: “bcda” OUTPUT: The strings are rotation of each other INPUT: String 1: “abcd” String 2: “bacd” OUTPUT: The strings are not in rotation of each other.
There are various methods to check if two strings are rotations of each other. Some of them are:
METHOD 1: Brute-Force Approach to check if two strings are rotations of each other
The brute-force solution of the given problem is to generate all possible rotation of first string and compare each rotation of the first string with second string. If any rotation of first string is equal to second string, then the given strings are rotation of each other. If no possible rotation of first string is equal to second string, then the given strings are not rotation of each other.The time complexity of this solution is O(n2), where ‘n’ is the length of the string.
C++ Program to check if two strings are rotations of each other is as follows:
/* C++ Program to check if two strings are rotations of each other */
#include<bits/stdc++.h>
using namespace std;
void checkStringRotation(string str1,string str2)
{
/* Check String length */
if(str1.length()!=str2.length())
cout<<"Strings are not in rotation of each other\n";
for(int i = 0 ; i< str1.length() ; i++)
{
char ch = str1[0];
// Erase first character of string str1
str1.erase(str1.begin()+0);
// Push it back at the end of string
str1.push_back(ch);
/* If any rotation is equal to string2,
then it is rotation of each other */
if(str1 == str2)
{
cout<<"Strings are in rotation of each other\n";
return;
}
}
cout<<"Strings are not in rotation of each other\n";
}
int main()
{
string str1,str2;
/* Scan strings */
cout<<"Enter string 1:\n";
cin>>str1;
cout<<"Enter string 2:\n";
cin>>str2;
/* Function to check string rotation */
checkStringRotation(str1,str2);
}
OUTPUT: Enter string 1: ABBA Enter string 2: BBAA Strings are in rotation of each other
METHOD 2: Efficient Method to check if two strings are rotations of each other
The efficient solution of the given problem is to concatenate first string with itself and called it as final_string. Then, search second in final_string. If second string is present in final_string as substring, then, the given strings are rotation of each other. Else, the given strings are not rotation of each other.
The time complexity of this solution is O(n^2), where ‘n’ is the length of the string.
C++ Program to check if two strings are rotations of each other is as follows:
/* C++ Program to check if two strings are rotations of each other */
#include<bits/stdc++.h>
using namespace std;
void checkStringRotation(string str1,string str2)
{
// If the length of the string are not same,
// The answer is false.
if(str1.length()!=str2.length())
cout<<"Strings are not in rotation of each other\n";
// Concatenate the string with itself
string final_string = str1 + str1;
if(final_string.find(str2) != string::npos)
cout<<"Strings are in rotation of each other\n";
else
cout<<"Strings are not in rotation of each other\n";
}
int main()
{
string str1,str2;
/* Scan String */
cout<<"Enter String1:\n";
cin>>str1;
cout<<"Enter String2:\n";
cin>>str2;
/* Function to check if strings are rotation of each other */
checkStringRotation(str1,str2);
}
OUTPUT: Enter string 1: ABBA Enter string 2: BBAA Strings are in rotation of each other
Related Posts:
- Program to check Palindromic Anagram.
- Program to print all the Palindromic Substring of the String.
- Program to check Panagram String.
- Program to find first non-repeating character of the String.
- Program to Reverse a String.
- Program to Count Number of Characters in a String.
- Program to Count frequency of particular character of the String.
- Program to Count Number of Vowels and Number of Consonants in a String.
- Program to Check if String is alphabetic or numeric or alpha-numeric.
- Program to copy one String to Another.
- Program to Concatenate Two Strings.
- Program to Check whether given String is Palindrome or not.
- Program to convert lower-case alphabet to upper-case alphabet and vice-versa.
- Program to count total number of words in a string.
- Program to find smallest and largest word of the String.
- Program to find Most Frequent Character of the String.
- Program to Remove all the blank spaces from the String.
- Program to check if String is isogram or not.
- Program to Reverse Each word of the String.
- Program to Print All the Substring of the Given String.
