【Python】字符串循环左移

小鱼儿 2022-05-22 00:42 189阅读 0赞

### 字符串循环左移 ###

> 给定一个字符串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