python字符串循環左移

2020-01-04 13:35:41

字體：大中小

來源：轉載

供稿：網友

本文實例為大家分享了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 -= 1if __name__ == '__main__': s = "abcdef" print(s) li = list(s); leftloop(li, 2) print(''.join(li))

輸出結果：