Python 寻找获得实际字符串所需的最小旋转次数的程序

理解如何有效处理字符串是一项基本的编程任务，可以显著提升我们代码的性能。从旋转字符串中找到产生所需字符串的最少旋转次数是一个有趣的字符串操作挑战。文本处理、密码学和数据压缩等情况经常涉及这个问题。

考虑这样一种情况，一个字符串被向右旋转了一定的次数。找到将字符串转换回原始形式所需的最少旋转次数是目标。通过解决这个问题，我们可以了解字符串的结构并获取有用的信息。

本文将探讨两种方法来确定从旋转字符串返回原始字符串所需的最少旋转次数。我们将使用Python这种灵活且受欢迎的编程语言来实践这些技术，Python以其可读性和易用性而闻名。

方法

在Python中搜索获得实际字符串的最小旋转次数，我们可以按照以下两种方法进行——

利用蛮力算法。
在用户定义的函数中利用while循环。

让我们详细讨论这两种方法——

方法一：利用蛮力算法

在蛮力算法中，将第一个字符串按所有可能的位置旋转，然后将第二个字符串与旋转后的第一个字符串进行比较。通过迭代所有可能的旋转，我们保持对获取第二个字符串所需最小旋转次数的跟踪。循环结束后，如果最小旋转变量仍为无穷大，则无法通过旋转第一个字符串来获取第二个字符串。如果不是，则返回所需旋转次数的最小值。该方法的时间复杂度为O(n^2)，其中n是第一个字符串的长度。

步骤

在Python中搜索获得实际字符串的最小旋转次数的步骤如下——

步骤1 − 创建一个具有两个字符串输入的函数。

步骤2 − 创建一个初始值为无穷大的变量，用于跟踪所需的最小旋转次数。

步骤3 − 从0到第一个字符串的长度，迭代可能的值。

步骤4 − 以当前索引位置旋转第一个字符串。这验证了第二个字符串和旋转后的字符串是否相等。如果是，则将变量的值更改为介于当前最小值和当前索引之间的最低值。

步骤5 − 如果最小旋转变量仍设置为无穷大，则返回-1（表示无法通过旋转第一个字符串来获取第二个字符串）。

步骤6 − 如果不是，则返回最小旋转变量。

示例

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)

输出

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

方法二：利用 while 循环在一个用户定义的函数中

有效的方法是使用连接的字符串来验证第二个字符串的存在，而不是进行显式的字符串旋转。如果由于两个字符串的长度不同而无法通过第一个字符串的旋转来恢复第二个字符串，则返回 -1。我们可以通过确定第二个字符串是否是连接字符串的子字符串来确定有多少次旋转是必要的，以将第二个字符串与第一个字符串分离开来。为了确定最小旋转次数，如果发现第二个字符串是一个子字符串，我们计算其索引并将其除以第一个字符串的长度。这种方法的时间复杂度为 O(n)，其中 n 是第一个字符串的长度。

步骤

在 Python 中搜索获得实际字符串的最小旋转次数的步骤如下：

第一步 - 创建一个带有两个字符串作为输入的函数。

第二步 - 如果两个字符串的长度不相等，则返回 -1（因为无法通过旋转第一个字符串来获得第二个字符串）。

第三步 - 通过将第一个字符串与其自身连接来创建一个临时字符串。

第四步 - 如果第二个字符串是临时字符串的子字符串，则返回第二个字符串在临时字符串中的索引除以第一个字符串的长度作为最小旋转次数。

第五步 - 如果不是，则返回 -1。

示例

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)

输出

String 1: program
String 2: grampro
Minimum rotations  3

结论

在本文中，我们介绍了两种方法来计算将给定字符串转化为另一个字符串所需的最小旋转次数。虽然第二种方法使用连续的字符串来检查第二个字符串的存在，而蛮力方法则通过每个可行的位置旋转第一个字符串。根据输入的大小和所需的效率，你可以选择最佳策略来解决这个问题。现在，通过掌握这些方法，你可以计算出从给定字符串中提取目标字符串所需的最少旋转次数。