Python program: Find the minimum number of rotations required to get the actual string?

Understanding how to handle strings efficiently is a fundamental programming task that can significantly improve the performance of your code. Finding the minimum number of rotations required to produce a desired string from a rotated string is an interesting challenge in string manipulation. Situations such as text processing, cryptography, and data compression often involve this problem.

Consider the situation where the string is rotated to the right by a certain amount. The goal is to find the minimum number of rotations required to convert the string back to its original form. By finding the solution to this problem, we can learn more about the string structure and obtain useful information.

This article will examine two methods for determining the minimum number of rotations required to return the original string from a rotated string. Python, a flexible and popular programming language known for its readability and ease of use, will be used to put these technologies into practice.

method

To search in Python to get the minimum number of rotations of an actual string, we can follow two methods -

• Use brute force.

• Use while loops in user-defined functions.

Let’s examine these two methods -

Method 1: Use brute force

Use a brute force method to rotate the first string in all possible positions, then compare the second string to the rotated first string. We keep track of the minimum number of rotations required to obtain the second string by iterating over all feasible rotations. After the loop ends, if the minimum rotation variable is still infinity, it is impossible to get the second string by rotating the first string. If not, we return the minimum number of spins required. The time complexity of this method is O(n^2), where n is the length of the first string.

algorithm

The steps to search for the minimum number of rotations in Python to get the actual string are as follows -

Step 1- Create a function that takes two strings as input.

Step 2 - Create a variable with an initial value of infinity to keep track of the minimum number of spins required.

Step 3 - From 0 to the length of the first string, iterate through the possible values.

Step 4- The first string should be rotated by the current index position. This verifies that the second string and the rotated string are equal. If so, change the variable's value to the minimum value between the current minimum value and the current index.

Step 5− If the minimum rotation variable is still set to infinity, then -1 is returned (indicating that it is not feasible to retrieve the second string by rotating the first string).

Step 6 - If not, return the minimum rotation variable.

Example

def min_rotations_bf(s1, s2):
   min_rotations = float('inf')

   for i in range(len(s1)):
      rotated = s1[i:] + s1[:i]
      if rotated == s2:
         min_rotations = min(min_rotations, i)

   if min_rotations == float('inf'):
      return -1
   else:
      return min_rotations


# Example usage
s1 = "program"
s2 = "grampro"
bf_result = min_rotations_bf(s1, s2)

print("String 1:", s1)
print("String 2:", s2)
print("Minimum rotations (Brute Force):", bf_result)

Output

String 1: program
String 2: grampro
Minimum rotations (Brute Force): 3

Method 2: Use a while loop in a user-defined function

What works is to use the concatenated string to verify that the second string exists, rather than doing explicit string rotation. If the second string cannot be retrieved by rotation of the first string because the two strings are of different lengths, we return -1. By determining whether the second string is a substring of the concatenated string, we can figure out how many rotations are needed to separate the second string from the first. To determine the minimum number of rotations, if the second string is found as a substring, we calculate the index and divide it by the length of the first string. The time complexity of this method is O(n), where n is the length of the first string.

algorithm

The steps to search for the minimum number of rotations in Python to get the actual string are as follows -

Step 1- Create a function that takes two strings as input.

Step 2 - If the lengths of the two strings are not equal, return -1 (because the second string cannot be obtained by rotating the first string).

Step 3 - Create a temporary string by concatenating the first string with itself.

Step 4 - If the second string is a substring of the temporary string, return the minimum number of rotations required divided by the index of the second string in the temporary string Take the length of the first string.

Step 5− If not, return -1.

Example

def min_rotations_efficient(s1, s2):
   if len(s1) != len(s2):
      return -1

   rotations = 0
   n = len(s1)

   # Check for left rotations
   while rotations < n:
      if s1 == s2:
         return rotations
      s1 = s1[1:] + s1[0]
      rotations += 1

   # Check for right rotations
   s1 = s1[-1] + s1[:-1]
   rotations = 1

   while rotations <= n:
      if s1 == s2:
         return rotations
      s1 = s1[-1] + s1[:-1]
      rotations += 1

   return -1
# Example usage
s1 = "program"
s2 = "grampro"
efficient_result = min_rotations_efficient(s1, s2)

print("String 1:", s1)
print("String 2:", s2)
print("Minimum rotations ", efficient_result)

Output

String 1: program
String 2: grampro
Minimum rotations  3

in conclusion

In this article, we looked at two methods of calculating the minimum number of rotations required to convert a given string into another string. The second method uses the concatenated strings to check if the second string exists, while the brute force method rotates the first string every feasible number of positions. One can choose the best strategy to solve this problem in Python depending on the size of the input and the required efficiency. Thanks to these methods, you can now calculate the minimum number of rotations required to extract a target string from a given string.

The above is the detailed content of Python program: Find the minimum number of rotations required to get the actual string?. For more information, please follow other related articles on the PHP Chinese website!