String – Is one string Rotation of other?

Assume you have a method isSubstring which checks if one word is a substring
of another. In C# you can use string.contains. Given two strings, str1 and str2, write code to check if str2 is a rotation of str1, using only one call to isSubstring / string.contains (e.g. “olAam” is a rotation of “Aamol”).

If we imagine that str2 is a rotation of str1, then we can ask what the rotation point is. For example, if you rotate Aamol after “Aam”, you get “olAam”. In a rotation, we
cut str1 into two parts x and y, and rearrange them to get str2.
str1 = xy = Aamol
x= Aam
y= ol
str2 = yx = olAam

So, we need to check if there’s a way to split str1 into x and y such that xy = str1 and yx = str2. Regardless of where the division between x and y is, we can see that yx will always be a substring of xyxy. That is str2 will always be a substring of str1str1. That’s how we solve the problem: simply do isSubstring(str1str1, str2).

        /// <summary>
        /// Determines whether the specified STR1 is rotation.
        /// </summary>
        /// <param name="str1">The STR1 - Original String </param>
        /// <param name="str2">The STR2 - Rotated String</param>
        /// <returns></returns>
        public static bool IsRotation(string str1, string str2)
        {
            //Check if str1 and str2 are equal length and not empty
            if (!string.IsNullOrEmpty(str1) &&
                !string.IsNullOrEmpty(str2) &&
                str1.Length == str2.Length)
            {
                /* Concatenate str1 and str2 in a new string */
                string str1str1 = str1 + str1;
                return str1str1.Contains(str2);
            }
            return false;
        }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s