字符串是由若干字符组成的有限序列，也可以理解为一个字符数组

344. 反转字符串

思路：双指针法。定义两个指针（即索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素

反转链表和反转字符串都是双指针法，但字符串也是一种数组，故元素在内存中是连续分布的（跟链表不同）

class Solution:def reverseString(self, s: List[str]) -> None:"""Do not return anything, modify s in-place instead."""i, j = 0, len(s)-1for i in range(len(s)):if i < j:s[i], s[j] = s[j], s[i]i += 1j -= 1return s

541. 反转字符串II

541. 反转字符串 II

题意简单概括：对于字符串s，每次遍历其2k的长度，反转2k长度里的前k个；若最后一组的长度不足2k但大于k，只反转这k个；若不足k，全部反转

首先，这题可以调用 344题反转字符串中的函数，但要注意的是，344题的输入是一个字符组成的列表，而这题是字符串

对字符串str 转字符列表 list，用 list() 即可
字符列表res 拼接回字符串，用 "".join(res)

其次，分析本题哪些部分需要反转。注意，对于字符串s，是2k个长度去遍历的。对于2k个长度中的前k个进行反转

使用 range(start, end, step) 来确定需要调换的初始位置
对于字符串s = 'abc'，如果使用s[0:999] ===> 'abc'。字符串末尾如果超过最大长度，则会返回至字符串最后一个值，这个特性可以避免一些边界条件的处理
用切片整体替换，而不是一个个替换

class Solution:def reverseStr(self, s: str, k: int) -> str:# 先定义一个反转函数def reverse(s):   # List[str]i, j = 0, len(s)-1for i in range(len(s)):if i < j:s[i], s[j] = s[j], s[i]i += 1j -= 1return sres = list(s)   # str —> listfor i in range(0, len(s), 2*k):  # 每次跳2k步res[i: i+k] = reverse(res[i: i+k])   # 切片是左闭右开return ''.join(res)

剑指offer 05. 替换空格

剑指 Offer 05. 替换空格

因为Python中字符串是不可变类型，所以操作字符串需要将其转换为列表，因此空间复杂度不可能为O(1)

法1：比较直观的一种方法。添加空列表，添加匹配的结果

class Solution:def replaceSpace(self, s: str) -> str:res = []for i in range(len(s)):if s[i] != ' ':   # 注意引号中间要打一个空格res.append(s[i])else:res.append('%20')return "".join(res)

法2：双指针。首先扩充数组到每个空格替换成 %20 之后的大小，然后从后向前替换空格（为什么是从后向前？因为从前向后填充的话，每次添加元素都要将添加元素之后的所有元素向后移动）

很多数组填充类的问题，都可以预先给数组扩容成填充后的大小，然后再从后向前进行操作

class Solution:def replaceSpace(self, s: str) -> str:cnt = s.count(' ')   # 统计字符串s里有多少个空格res = list(s)   # str —> listres.extend([' ']*2*cnt)  # 每个空格都要换成%20，长度+2# left遍历s，若遇到空格，则替换为%20；否则直接赋给rightleft, right = len(s)-1, len(res)-1   # 从后向前遍历while left >= 0:if res[left] != ' ':res[right] = res[left]right -= 1else:res[right-2: right+1] = '%20'   # 左闭右开 [right-2, right)right -= 3left -= 1return "".join(res)

151. 反转字符串中的单词

思路：移除多余空格（双指针法） —> 将整个字符串反转 —> 将每个单词反转（先整体反转再局部反转）

class Solution:def reverseWords(self, s: str) -> str:s = s.strip()   # 先去除字符串前后的空格s = s[::-1]   # 反转整个字符串s = ' '.join(word[::-1] for word in s.split())   # 将每个单词反转return s

若不借助 strip() 和 split() 函数，写起来很麻烦，代码如下：

class Solution:# 反转s[i: j]def reverse(self, s, i, j):   # s是一个listwhile i < j:s[i], s[j] = s[j], s[i]i += 1j -= 1def reverseWords(self, s: str) -> str:s = list(s)# strip()start, end = 0, len(s) - 1n = len(s)while start < n and s[start] == ' ':start += 1while end >= 0 and s[end] == ' ':end -= 1if start > end:return ''# 去除中间多余的空格, 并且把字符串挪到最前面        i, j = 0, startwhile j <= end:if s[j] == ' ':if s[j - 1] == ' ':   # 多个空格j += 1else:s[i] = s[j]   # 只有1个空格i += 1j += 1else:   # 字母s[i] = s[j]i += 1j += 1n = i   # 有效字符串的长度self.reverse(s, 0, n - 1)i = 0while i < n:j = i # 找到i开始的整个单词while j < n and s[j] != ' ':j += 1# 此时, j指向单词的最后一个字母后的空格或者字符串结束处self.reverse(s, i, j - 1)i = j + 1 # 跳到下个单词的第一个return ''.join(s[:n])   # n是有效字符串的长度

剑指Offer58-II.左旋转字符串

剑指 Offer 58 - II. 左旋转字符串

使用整体反转+局部反转就可以实现反转单词顺序的目的

思路：先局部反转再整体反转

class Solution:def reverse(self, s: list, start, end):while start < end:s[start], s[end] = s[end], s[start]start += 1end -= 1def reverseLeftWords(self, s: str, n: int) -> str:# 先反转前n个res = list(s)self.reverse(res, 0, n-1)# 再反转n+1到末尾self.reverse(res, n, len(res)-1)# 再整个反转self.reverse(res, 0, len(res)-1)return "".join(res)

28. 找出字符串中第一个匹配项的下标

（一）KMP

KMP主要应用在字符串匹配的场景中，其思想是当出现字符串不匹配的情况时，可以知道一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配

如：文本串aabaabaaf（长度为n），模式串aabaaf（长度为m），要在文本串里匹配模式串

暴力：两层for循环，遍历两个字符串，挨个匹配。时间复杂度O(m*n)
KMP：匹配过程O(n)，单独生成next数组是O(m)。时间复杂度O(m+n)

next数组是一个前缀表，用来回退，记录了模式串与文本串不匹配时，模式串应该从哪里开始重新匹配。定义前缀表为：记录下标i（包括i）之前的字符串中有多长的相同前后缀

前缀：包含首字母，不包含尾字母的所有连续子串
后缀：包含尾字母，不包含首字母的所有连续子串

求得最长相同前后缀的长度就是对应前缀表的元素。找到了最长相等的前后缀，匹配失败的位置是后缀子字符串的后一个字符，找到与其相同的前缀，从后面重新匹配即可

关键：寻找匹配失败位置的前一位在前缀表中的元素，即为要跳转到的重新匹配的下标位置

（二）代码

class Solution:# 构造next数组，即前缀表（将前缀表直接作为next数组）def getNext(self, next: List[int], s: str):    # s为模式串# step1：初始化next数组j = 0   # j为前缀末尾位置next[0] = 0   # 只有一个字符的字符串相同前后缀的最大长度是0for i in range(1, len(s)):   # i为后缀末尾位置# step2：若前缀和后缀对应的字符不相同while s[i] != s[j] and j>0:   # 是while而不是if，因为若不相同要连续回退j = next[j-1]   # j要回退到前一位next数组的值的下标位置# step3：若前缀和后缀对应的字符相同if s[i] == s[j]:j += 1   # j还代表着i包括i之前子串的最长相等前后缀长度next[i] = j # 在haystack(文本串)里匹配needle(模式串)def strStr(self, haystack: str, needle: str) -> int:next = [0]*len(needle)self.getNext(next, needle)j = 0   # j为模式串起始位置for i in range(len(haystack)):   # i为文本串起始位置while haystack[i] != needle[j] and j>0:j = next[j-1]   # j就要从next数组中寻找下一个匹配的位置if haystack[i] == needle[j]:j += 1  # 若相同, i和j同时向后移动if j == len(needle):   # 若j指向了模式串的末尾，说明模式串完全匹配文本串的某个子串了return i-len(needle)+1   # 返回模式串在文本串中匹配时的第一个字符的位置return -1

459. 重复的子字符串

复习KMP：

适用场景：给你一个字符串，判断另一个字符串是不是在这个字符串里出现过
KMP算法在查找过程中遇到不匹配的地方，直接跳到上一次匹配的地方继续匹配（因为有计算好的next数组）
next数组：以各个字符串为结尾的子串的最长相等前后缀的集合

若一个字符串是由重复子串组成的，那么它的最小重复单位就是它的最长相等前后缀不包含的那个子串。如：字符串 abababab，最长相等前后缀为 ababab，故不包含的就是ab

数组长度 - 最长相等前后缀的长度，相当于第一个重复子串的长度，也就是一个重复周期的长度。如果这个周期可以被整除，说明整个数组就是这个周期的循环

class Solution:# KMP求next数组(记录的就是最长相等前后缀的长度)def getNext(self, next: List[int], s: str):j = 0next[0] = 0for i in range(1, len(s)):while s[i] != s[j] and j>0:j = next[j-1]if s[i] == s[j]:j += 1next[i] = jdef repeatedSubstringPattern(self, s: str) -> bool:next = [0]*len(s)self.getNext(next, s)   # "ababab"  [0,0,1,2,3,4]# next[-1] != 0说明字符串有相同的前后缀# next[-1] 就是最长相等前后缀的长度# len(s)-next[-1] 就是重复子串的长度if next[-1] != 0 and len(s) % (len(s)-next[-1]) == 0:   return Trueelse:return False

总结：使用KMP可以解决两类经典问题，匹配问题（28题）和重复子串问题（459题）