剑指Offer58-II左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

示例1:

输入：s = "abcdefg", k = 2
输出："cdefgab"

示例2：

输入：s = "lrloseumgh", k = 6
输出："umghlrlose"

限制：

• 1 <= k < s.length <= 10000

class Solution:
	def reverseLeftWords(self, s, n):

解题思路：

本题解法较多，本文主要介绍字符串切片，列表遍历拼接，字符串遍历拼接三种方法。

方法一：字符串切片

应用字符串切片函数，可方便实现左旋转字符串。

获取字符串s[n:]切片和s[:n]切片，使用”+”运算符拼接并返回即可。

复杂度分析：

• 时间复杂度O(N):其中N为字符串s的长度，字符串切片函数为线性时间复杂度。
• 空间复杂度O(N):两个字符串切片的总长度为N。

class Solution:
	def reverseLeftWords(self, s, n):
		return s[n:]+s[:n]

方法二：列表遍历拼接

若面试规定不允许使用切片函数，则使用此方法。

算法流程：

1. 新建一个list(Python)，记为res；
2. 先将res添加”第n+1位至末位的字符”；
3. 再将res添加”首位至第n位的字符”；
4. 将res转换为字符串并返回。

复杂度分析:

• 时间复杂度O(N):线性遍历s并添加，使用线性时间。
• 空间复杂度O(N):新建的辅助res使用O(N)大小的额外空间。

class Solution:
	def reverseLeftWords(self, s, n):
		res = []
		for i in range(n, len(s)):
			res.append(s[i])
		for i in range(n):
			res.append(s[i])
		return ''.join(res)

利用求余运算，可以简化代码。

class Solution:
	def reverseLeftWords(self, s, n):
		res = []
		for i in range(n, n+len(s)):
			res.append(s[i % len(s)])
		return "".join(res)

方法三：字符串遍历拼接

若规定Python不能使用join函数，或规定Java只能使用String，则使用此方法。

此方法与方法二思路一致，区别是使用字符串代替列表。

复杂度分析:

• 时间复杂度O(N):线性遍历s并添加，使用线性时间。
• 空间复杂度O(N):假设循环过程中内存会被及时回收，内存中至少同时存在长度为N和N-1的两个字符串(新建长度为N的res需要使用前一个长度N-1的res)，因此至少使用O(N)的额外空间。

class Solution:
	def reverseLeftWords(self, s, n):
		res = ""
		for i in range(n, len(s)):
			res += s[i]
		for i in range(n):
			res += s[i]
        # for i in range(n, n+len(s)):
       	# 	res += s[i%len(s)]
		return res