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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Karan
Guest

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

Bhoomika Panwar
Guest

No. It is fine. As with each iteration, we are rotating the already rotated string as the rotate function modifies the string itself.