Check if strings can be derived from each other by circularly rotating them

Check if given string can be derived from another string by circularly rotating it. The rotation can be in clockwise or anti-clockwise rotation.


 

For example,


Input:
X = ABCD
Y = DABC

Output: Yes

Y can be derived from X by right-rotating string X by 1 unit

 
For two given strings X and Y, a simple solution would be to check if string Y is sub-string of string XX or not. If yes, they can be derived from each other. For example, consider string X = ABCD and Y = DABC

XX = ABCD + ABCD = ABCDABCD

string Y is clearly a substring of ABCDABCD

The implementation can be seen here. This solution seems efficient but it is using O(n) extra space.
 

How to do this using O(1) space ?
 
The idea is to in-place rotate the string X and check if it becomes equal to string Y or not. We have to consider every possible rotation of string X (i.e. rotation by 1 unit, 2 unit.. till n-1 unit where n is the length of string X). Note that clockwise or anti-clockwise rotation doesn’t matter.

 
Below is C++ and Java implementation of the idea –

C++

Download   Run Code

Java

Download   Run Code

Output:

Given strings can be derived from each other

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Get great deals at Amazon




Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Karan
Guest
Karan

In the for loop, I think it should be rotate(X.begin(), X.begin()+I, X.end()) since we are checking for each rotation.

wpDiscuz