您好,登錄后才能下訂單哦!
本文實(shí)例為大家分享了python字符串循環(huán)左移的具體代碼,供大家參考,具體內(nèi)容如下
字符串循環(huán)左移
給定一個字符串S[0…N-1],要求把S的前k個字符移動到S的尾部,如把字符串“abcdef”前面的2個字符‘a(chǎn)'、‘b'移動到字符串的尾部,得到新字符串“cdefab”:即字符串循環(huán)左移k位。
循環(huán)左移k位等價于循環(huán)右移n-k位。算法要求:
時間復(fù)雜度為 O(n),空間復(fù)雜度為 O(1)。
分析思路:
暴力移位:
每次循環(huán)左移1位,調(diào)用k次即可
時間復(fù)雜度O(kN),空間復(fù)雜度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]
時間復(fù)雜度O(N),空間復(fù)雜度O(k),不符合要求
三次翻轉(zhuǎn):
(X'Y')'=YX
如:abcdef
X=ab X'=ba
Y=cdef Y'=fedc
(X'Y')'=(bafedc)'=cdefab
時間復(fù)雜度O(N),空間復(fù)雜度O(1),符合要求
Python代碼如下:
# 在Python中字符串類型 'str' 不支持給它的item賦值,我們這里用list代替字符串 def leftloop(s, k): """ 字符串循環(huán)左移 :param s: 字符串?dāng)?shù)組 :param k: 字符串循環(huán)左移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): """ 翻轉(zhuǎn) :param s: 字符串?dāng)?shù)組 :param i: 翻轉(zhuǎn)開始位置 :param j: 翻轉(zhuǎn)結(jié)束位置 """ 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))
輸出結(jié)果:
abcdef
cdefab
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持億速云。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。