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 1. 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) 登录后复制