Checking for string rotations →
Today, let us play with some examples using “strings”. Let us see if we can write a function which, given two strings, would tell you if the input strings are rotations of each other. For example, anna
and naan
are rotations of each other while anna
and nana
are not. More simply, two strings are rotations if you can get from on to the other while moving the characters in order (without over-stepping):
a-n-n-a --> 0. original string
n-n-a-a --> 1. rotated by 1 ('a' moves to the end)
n-a-a-n --> 2. rotated by 1
A very simple algorithm would just concatenate one of the input strings with itself and try to find the second string in the concatenation of the first. In the above example, this would be:
- Concatenate one of the strings with itself. Say, we choose
anna
to concatenate and form the concatenated oneannaanna
- Search for the occurence of the second string
naan
in the concatenation, - We see that
naan
is indeed a substring of the concatenation annaanna and a rotation ofanna
.
A caveat here is to check for the length of the two strings a priori. This is to avoid sub-strings of smaller length that would be identified as rotations by our algorithm. For example, without this check, we would deduce ann
to be a rotation of anna
.