搜索
首页后端开发Python教程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 中的这一问题。由于掌握了这些方法,您现在可以计算从给定字符串中提取目标字符串所需的最低旋转次数。

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

声明
本文转载于:tutorialspoint。如有侵权,请联系admin@php.cn删除
Python和时间:充分利用您的学习时间Python和时间:充分利用您的学习时间Apr 14, 2025 am 12:02 AM

要在有限的时间内最大化学习Python的效率,可以使用Python的datetime、time和schedule模块。1.datetime模块用于记录和规划学习时间。2.time模块帮助设置学习和休息时间。3.schedule模块自动化安排每周学习任务。

Python:游戏,Guis等Python:游戏,Guis等Apr 13, 2025 am 12:14 AM

Python在游戏和GUI开发中表现出色。1)游戏开发使用Pygame,提供绘图、音频等功能,适合创建2D游戏。2)GUI开发可选择Tkinter或PyQt,Tkinter简单易用,PyQt功能丰富,适合专业开发。

Python vs.C:申请和用例Python vs.C:申请和用例Apr 12, 2025 am 12:01 AM

Python适合数据科学、Web开发和自动化任务,而C 适用于系统编程、游戏开发和嵌入式系统。 Python以简洁和强大的生态系统着称,C 则以高性能和底层控制能力闻名。

2小时的Python计划:一种现实的方法2小时的Python计划:一种现实的方法Apr 11, 2025 am 12:04 AM

2小时内可以学会Python的基本编程概念和技能。1.学习变量和数据类型,2.掌握控制流(条件语句和循环),3.理解函数的定义和使用,4.通过简单示例和代码片段快速上手Python编程。

Python:探索其主要应用程序Python:探索其主要应用程序Apr 10, 2025 am 09:41 AM

Python在web开发、数据科学、机器学习、自动化和脚本编写等领域有广泛应用。1)在web开发中,Django和Flask框架简化了开发过程。2)数据科学和机器学习领域,NumPy、Pandas、Scikit-learn和TensorFlow库提供了强大支持。3)自动化和脚本编写方面,Python适用于自动化测试和系统管理等任务。

您可以在2小时内学到多少python?您可以在2小时内学到多少python?Apr 09, 2025 pm 04:33 PM

两小时内可以学到Python的基础知识。1.学习变量和数据类型,2.掌握控制结构如if语句和循环,3.了解函数的定义和使用。这些将帮助你开始编写简单的Python程序。

如何在10小时内通过项目和问题驱动的方式教计算机小白编程基础?如何在10小时内通过项目和问题驱动的方式教计算机小白编程基础?Apr 02, 2025 am 07:18 AM

如何在10小时内教计算机小白编程基础?如果你只有10个小时来教计算机小白一些编程知识,你会选择教些什么�...

如何在使用 Fiddler Everywhere 进行中间人读取时避免被浏览器检测到?如何在使用 Fiddler Everywhere 进行中间人读取时避免被浏览器检测到?Apr 02, 2025 am 07:15 AM

使用FiddlerEverywhere进行中间人读取时如何避免被检测到当你使用FiddlerEverywhere...

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解锁Myrise中的所有内容
4 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

功能强大的PHP集成开发环境

SublimeText3 英文版

SublimeText3 英文版

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

DVWA

DVWA

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

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能