搜索
首页后端开发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之Seaborn(数据可视化)详细讲解Python之Seaborn(数据可视化)Apr 21, 2022 pm 06:08 PM

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

详细了解Python进程池与进程锁详细了解Python进程池与进程锁May 10, 2022 pm 06:11 PM

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

Python自动化实践之筛选简历Python自动化实践之筛选简历Jun 07, 2022 pm 06:59 PM

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

归纳总结Python标准库归纳总结Python标准库May 03, 2022 am 09:00 AM

本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于标准库总结的相关问题,下面一起来看一下,希望对大家有帮助。

分享10款高效的VSCode插件,总有一款能够惊艳到你!!分享10款高效的VSCode插件,总有一款能够惊艳到你!!Mar 09, 2021 am 10:15 AM

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

python中文是什么意思python中文是什么意思Jun 24, 2019 pm 02:22 PM

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

Python数据类型详解之字符串、数字Python数据类型详解之字符串、数字Apr 27, 2022 pm 07:27 PM

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

详细介绍python的numpy模块详细介绍python的numpy模块May 19, 2022 am 11:43 AM

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

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.能量晶体解释及其做什么(黄色晶体)
2 周前By尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

安全考试浏览器

安全考试浏览器

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

DVWA

DVWA

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

SublimeText3 英文版

SublimeText3 英文版

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

EditPlus 中文破解版

EditPlus 中文破解版

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

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版