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 中的这一问题。由于掌握了这些方法，您现在可以计算从给定字符串中提取目标字符串所需的最低旋转次数。

以上是Python程序：找到获取实际字符串所需的最小旋转次数？的详细内容。更多信息请关注PHP中文网其他相关文章！