Check if Strings are Rotations 🎯

Welcome to another engaging tutorial at CodeYourCraft! Today, we're diving into a fascinating topic - String Rotations. This lesson is perfect for both beginners and intermediates looking to expand their algorithmic skills. Let's get started!

What are String Rotations? 📝

String rotations occur when one string is a substring of another, but in a different order. For example, consider the strings waterbottle and erbottlewater. The second string is a rotation of the first.

Why are String Rotations Important? 💡

String rotations are essential in various real-world scenarios, such as password security, DNA sequencing, and even cryptography. Understanding how to check for string rotations can help you solve complex problems and upskill as a developer.

The Algorithm 💡

To determine if two strings are rotations, we'll compare the two strings by concatenating them and checking if the resulting string contains the first string as a substring.

Pseudocode 📝

Concatenate the two input strings (str1 and str2)
Check if the concatenated string contains str1 as a substring
If found, return true (the strings are rotations)
If not found, return false (the strings are not rotations)

Example ✅

Let's examine a simple example:

python

def are_rotations(str1, str2):
    combined = str1 + str2
    if str1 in combined[len(str2):]:
        return True
    else:
        return False

str1 = "waterbottle"
str2 = "erbottlewater"
print(are_rotations(str1, str2))  # Output: True

In this example, we defined a function called are_rotations that takes two strings as input. It concatenates the two strings, checks if the resulting string contains the first string, and returns the result.

Optimization 💡

The above algorithm works, but it's not the most efficient solution. A more optimized version can be achieved by cutting the smaller string and checking its position in the larger string.

Pseudocode 📝

Determine the length of the shorter string (str1 or str2)
Loop through the shorter string, checking if it's a substring of the longer string at each position.
If found, return true (the strings are rotations)
If not found after checking all possible positions, return false (the strings are not rotations)

Example ✅

python

def are_rotations(str1, str2):
    if len(str1) > len(str2):
        shorter, longer = str2, str1
    else:
        shorter, longer = str1, str2

    for i in range(len(longer) - len(shorter) + 1):
        if shorter == longer[i:i+len(shorter)]:
            return True
    return False

str1 = "waterbottle"
str2 = "erbottlewater"
print(are_rotations(str1, str2))  # Output: True

In this example, we optimized the algorithm to check for string rotations more efficiently. First, we determined the shorter string and looped through it, checking its position in the longer string.

Quiz 🎯

That's it for today! Practice the algorithm and feel free to reach out if you have any questions or need further clarification. Happy coding! 🎯💻🚀