Python实现字符串循环左移：三次翻转法详解

Python字符串循环左移概述

本文分享了一个Python实现字符串循环左移的具体代码示例，供读者参考学习。

字符串循环左移

假设有一个字符串S，索引范围为0到N-1，目标是将S的前k个字符移动到S的末尾。例如，对于字符串“abcdef”，将其前2个字符‘a’和‘b’移至尾部，结果变为“cdefab”，这被称为字符串循环左移k位。此外，循环左移k位在数学上等价于循环右移N-k位。

算法性能要求：

必须满足时间复杂度为O(n)，且空间复杂度控制在O(1)。

算法思路与复杂度分析

以下是具体的思路分析：

暴力移位法：

该方法每次仅左移1位，重复执行k次即可完成。虽然空间复杂度为O(1)，但其时间复杂度高达O(kN)，不符合题目对效率的要求。

三次拷贝法：

具体步骤为：先将S的前k个字符S[0…k]拷贝至临时数组T[0…k]；接着将S[k+1…N-1]拷贝至S的起始位置S[0…N-k-1]；最后将T[0…k]拷贝至S的尾部S[N-k…N-1]。此方法时间复杂度为O(N)，但空间复杂度为O(k)，同样不符合O(1)空间的要求。

三次翻转法：

核心原理为(X'Y')'=YX，其中'表示翻转操作。以“abcdef”为例：设X=“ab”，Y=“cdef”，则X'=“ba”，Y'=“fedc”。先分别翻转X和Y得到“bafedc”，再整体翻转一次，即(bafedc)'，最终结果为“cdefab”。该算法时间复杂度为O(N)，空间复杂度为O(1)，完全符合题目要求。

Python代码实现与测试

Python参考代码如下：

# 在Python中字符串类型 'str' 不支持给它的item赋值，我们这里用list代替字符串

def leftloop(s, k):
 """
 字符串循环左移
 :param s: 字符串数组
 :param k: 字符串循环左移k位
 :return:
 """
 if s is None:
 return
 n = len(s)
 if n < k:
 return
 reverse(s, 0, k - 1)
 reverse(s, k, n - 1)
 reverse(s, 0, n - 1)


def reverse(s, i, j):
 """
 翻转
 :param s: 字符串数组
 :param i: 翻转开始位置
 :param j: 翻转结束位置
 """
 if s is None or i < 0 or j < 0 or i >= j or len(s) < j + 1:
 return
 while i < j:
 temp = s[i]
 s[i] = s[j]
 s[j] = temp
 i += 1
 j -= 1


if __name__ == '__main__':
 s = "abcdef"
 print(s)
 li = list(s);
 leftloop(li, 2)
 print(''.join(li))

程序运行输出结果如下：

abcdef cdefab

以上是关于Python字符串循环左移的全部内容，希望本示例能对读者有所帮助，欢迎继续支持本站获取更多技术资源。