了解如何有效地处理字符串是一项基本的编程任务,可以显着提高代码的性能。找到从旋转的弦产生所需弦所需的最少旋转次数是弦操作中的一个有趣的挑战。文本处理、密码学和数据压缩等情况经常涉及到这个问题。
考虑字符串向右旋转一定量的情况。目标是找到将字符串转回其原始形式所需的最少旋转次数。通过找到该问题的解决方案,我们可以了解有关字符串结构的更多信息并获取有用的信息。
本文将研究两种方法,用于确定从旋转字符串返回原始字符串所需的最少旋转次数。 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中文网其他相关文章!

本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于Seaborn的相关问题,包括了数据可视化处理的散点图、折线图、条形图等等内容,下面一起来看一下,希望对大家有帮助。

本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于进程池与进程锁的相关问题,包括进程池的创建模块,进程池函数等等内容,下面一起来看一下,希望对大家有帮助。

本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于简历筛选的相关问题,包括了定义 ReadDoc 类用以读取 word 文件以及定义 search_word 函数用以筛选的相关内容,下面一起来看一下,希望对大家有帮助。

VS Code的确是一款非常热门、有强大用户基础的一款开发工具。本文给大家介绍一下10款高效、好用的插件,能够让原本单薄的VS Code如虎添翼,开发效率顿时提升到一个新的阶段。

pythn的中文意思是巨蟒、蟒蛇。1989年圣诞节期间,Guido van Rossum在家闲的没事干,为了跟朋友庆祝圣诞节,决定发明一种全新的脚本语言。他很喜欢一个肥皂剧叫Monty Python,所以便把这门语言叫做python。

本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于数据类型之字符串、数字的相关问题,下面一起来看一下,希望对大家有帮助。

本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于numpy模块的相关问题,Numpy是Numerical Python extensions的缩写,字面意思是Python数值计算扩展,下面一起来看一下,希望对大家有帮助。


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

安全考试浏览器
Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

DVWA
Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

SublimeText3 英文版
推荐:为Win版本,支持代码提示!

EditPlus 中文破解版
体积小,语法高亮,不支持代码提示功能

SublimeText3 Linux新版
SublimeText3 Linux最新版