Python程序：查找获得实际字符串所需的最少旋转次数？

---

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

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

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

方法

为了在Python中查找获得实际字符串所需的最少旋转次数，我们可以遵循以下两种方法：

• 使用蛮力法。

• 在用户定义函数中使用while循环。

让我们研究这两种方法：

方法1：使用蛮力法

在蛮力法中，第一个字符串按所有可能的位移旋转，然后将第二个字符串与旋转后的第一个字符串进行比较。我们通过迭代所有可能的旋转来跟踪获得第二个字符串所需的最小旋转次数。循环结束后，如果最小旋转次数变量仍然是无穷大，则无法通过旋转第一个字符串来获得第二个字符串。如果不是，我们返回所需的最小旋转次数。此方法的时间复杂度为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

方法2：在用户定义函数中使用while循环

有效的方法使用连接的字符串来检查第二个字符串的存在，而不是进行显式的字符串旋转。如果由于两个字符串的长度不同而无法通过第一个字符串的旋转获得第二个字符串，我们返回-1。我们可以通过确定第二个字符串是否是连接字符串的子字符串来计算获得第二个字符串所需的旋转次数。如果找到第二个字符串作为子字符串，我们计算索引并将其除以第一个字符串的长度，以确定最少的旋转次数。此方法的时间复杂度为O(n)，其中n是第一个字符串的长度。

算法

在Python中查找获得实际字符串所需的最少旋转次数的步骤如下：

步骤1 - 创建一个函数，该函数以两个字符串作为输入。

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

步骤3 - 通过将第一个字符串自身连接起来创建一个临时字符串。

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

步骤5 - 如果不是，则返回-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

结论

在本文中，我们研究了两种计算将给定字符串转换为另一个字符串所需的最少旋转次数的方法。蛮力法通过所有可能的位移旋转第一个字符串，而第二种方法使用连接的字符串来检查第二个字符串的存在。可以根据输入的大小和所需的效率选择最佳方法来解决Python中的这个问题。通过掌握这些方法，您现在可以计算从给定字符串中提取目标字符串所需的最小旋转次数。