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.

 
C++ implementation –
 

Download   Run Code

Output:

Given strings are rotation of 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 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz