题目描述
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
请定义一个函数实现字符串左旋转操作的功能。
比如输入字符串”abcdefg”和数字2,该函数将返回左旋转2位得到的结果”cdefgab”。
注意:
数据保证n小于等于输入字符串的长度。
样例
输入:"abcdefg" , n=2
输出:"cdefgab"
算法1
(拼接字符串) $O(n)$
右半边字符串拼接左半边字符串
实际上占用了string的额外内存空间,最好用数组翻转
时间复杂度
时间复杂度$O(n)$,空间复杂度$O(n)$,
python代码
class Solution(object):
def leftRotateString(self, s, n):
"""
:type s: str
:type n: int
:rtype: str
"""
return s[n:] + s[:n]
算法2
(数组翻转) $O(n)$
- (1) 整个数组翻转
- (2) 左半边翻转
- (3) 右半边翻转
时间复杂度
时间复杂度$O(n)$,空间复杂度$O(1)$,
python 代码
class Solution(object):
def reverse(self, s, l, r):
"""
数组翻转
:type s: list(int)
:type l: int
:type r: int
"""
r -= 1
while l < r:
s[l], s[r] = s[r], s[l]
l += 1
r -= 1
def leftRotateString(self, s, n):
"""
左旋转字符串
:type s: str
:type n: int
:rtype: str
"""
if len(s) == 0 or n == 0: return s
s = list(s)
self.reverse(s, 0, len(s))
self.reverse(s, 0, len(s)-n)
self.reverse(s, len(s)-n, len(s))
return ''.join(s)