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(kN)，空间复杂度O(1)，不符合要求

三次拷贝： 

S[0…k] → T[0…k] 

S[k+1…N-1] → S[0…N-k-1] 

T[0…k] →S[N-k…N-1] 

时间复杂度O(N)，空间复杂度O(k)，不符合要求

三次翻转：

(X'Y')'=YX 

如：abcdef 

X=ab X'=ba 

Y=cdef Y'=fedc 

(X'Y')'=(bafedc)'=cdefab 

时间复杂度O(N)，空间复杂度O(1)，符合要求

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



以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持中文源码网。