代码随想录一刷笔记_字符串
60+在408的算法考察难度和深度上还是收手了👍）
反转字符串（344）
交换数值的两种方式：
使用一个中间变量传递
通过位运算（使用异或运算符^）
1
2
3s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
反转字符串Ⅱ（541）
题目条件的处理
这一题处理当前段字符串有三种情况，分别是：
- 当前段字符串字符数n = 2k，则要反转2k字符中的前k个字符
- 当前段字符串字符数n < k，则要将所有字符反转
- 当前段字符串字符数k <= n < 2k，则要反转前k个字符
比对一下，实际上1和3是可以合并的，都是反转当前段中的前k个字符，故只要判断条件2即可。
局部变量的传递
在不使用库函数的情况下，需要自己定义一个函数对字符串进行反转操作。如果只是在函数中传递字符串的副本，那么函数中对其的修改不会返回调用者中。
1
2
3
4
5// 只是传递字符串的副本
void reverse(string s, int i, int k)
// 引用字符串
void reverse(string& s, int i, int k)
替换数字（54）
这道题可以让空间复杂度为O(1)，做法是先预先给数组扩充带填充后的大小，然后从后向前进行操作。具体如下：
扩大原数组空间。
1
2// 扩充字符串大小的函数
s.resize(需要的大小)将字符串中的数字替代为‘number’字串
从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。
在面对数组填充类的问题时，从后向前进行填充不失为一种好方法。
翻转字符串里的单词（151）
常用的想法：先翻转整个字符串，然后再翻转各个单词，就可以实现调转单词顺序的效果！
注意&优化：
删除多余字符的操作（需要使用倒序遍历的思想！）
删除多余的‘ ’时会改变string.size()的大小，其中字符串内字符的index也会改变，如果使用倒序遍历的话，就可以避免这个问题。
降低时间复杂度
如果只是遍历一遍字符串然后删除‘ ’的话，时间复杂度会达到O(n^2)。有以下的修改方法：
快慢指针
使用快慢指针的方法，将输出的字符串部分挪到字符串的前半部分，然后抹除后半部分，时间复杂度仅为O(n)。
实现strStr()(28)
考察kmp算法的实现，算法的时间复杂度为O(m+n)
理论基础
前缀&后缀
- 前缀：包含首字母，不包含尾字母的所有子串
- 后缀：包含尾字母，不包含首字母的所有子串
求前缀表，就是求当前字符串中子串的最长相等前后缀的过程。然后，next数组有多种表现形式，不过都是基于前缀表来的（也有直接使用前缀表的），后面具体的调用next数组的过程也会有略微的不同。
具体实现
next数组的求法也就是求当前子串中的最长相等前后缀。可以分为4个步骤：
初始化
定义两个指针i和j。其中，i指向后缀末尾位置（循环遍历的是i），j指向前缀末尾位置（同时还承担计数最长相等前后缀的功能）。
处理前后缀不相同的情况
处理前后缀相同的情况
next数组赋值
重复的子字符串（459 ）
这一题有两种方法，分别是移动匹配和kmp算法的应用
移动匹配
用到了**str.substr(i, s.size())**方法。用于从字符串str中提取起始位置为i，长度为s.size()的字符串。
kmp算法的应用
思路：如果存在最小重复子串，那么最长相等前后缀不包含的子串就是 最小重复子串！（什么中文长难句👈(ﾟヮﾟ👈)）
对字符串s求next数组，我们可以得到最长相等的前后缀（其中，前缀和后缀分别去掉了尾字母和首字母。故，如果给到的字符串是由重复子串构成的，那么我们可以得到一个去了一层重复子串的最长相等前后缀。）
故，在得到最长相等前后缀后，可以通过判断最小重复子串和最长相等前后缀之间的size是否成比例达成目标。
Q：如何辨别字符串s是否有最长相等前后缀？
A：对s求next数组后，若next[s.size() - 1] != 0，则证明字符串s拥有长度为next[s.size() - 1]的最长相等前后缀。