string reflections

344. 反转字符串

题目：https://leetcode.cn/problems/reverse-string/description/

我的解答

这道题太简单了，用双指针法可以很轻易地解决，也没有什么边界条件细节要注意，别忘了移动指针就行

541. 反转字符串 II

题目：https://leetcode.cn/problems/reverse-string-ii/description/

我的解答

这题非常非常非常恶心，题目描述得也一点都不清晰，十分容易被误导，本质其实就是一个简单的反转字符串，却非要表述得绕来绕去的恶心人🤯

• 首先注意到题目给的是 string 字符串类型的，它底层是只读的，所以不能直接索引修改值，要用 []byte(s) 转成 byte 类型才能正常索引

• 所以我们要额外自己写一个反转函数 reverse，方便我们调用，正常用双指针法反转即可

• 题目的意思是将给出的字符串每 2k 个一组，分成多个数量为 2k 的组，然后由于最后一组可能包含的字母数量不足以 2k，所以给了分条件判断，按照不同条件来对每 2k 个字母进行反转，而不是以 2k 为界限前后分别操作

• 所以我们的 i 每次就跳 2k 个，来保证每次都刚好指向新的一组的第一个字母，然后进入循环后先算一下剩下还有几个字母，这里的剩余字符指的是从当前的 i 索引到的字母一直到最后一个字母，而不是 2k + 1 到最后一个

• 所以分好组之后直接进入判断然后反转就可以了，这里用 go 的切片传递给 reverse 的时候要注意，切片的区间是左闭右开的，中间用冒号连接，所以右边界是不用额外 -1 的

• 最后将 byte 类型的结果用 string() 转回去再返回即可

151. 反转字符串中的单词

题目：https://leetcode.cn/problems/reverse-words-in-a-string/description/

我的解答

这道题如果对于 go 的 strings 标准库比较熟悉的话会发现，先用 Fields 函数取出各个单词，再用 Join 函数组合，这题就非常轻松地解决了，我也提供了示例做法，但我们在面试时如果面试官要求不能使用库函数的话，自己也要会实现才行，下面是具体做法，稍微有一些复杂：

• 我们首先要从题目给的字符串中取出所有单词

  • 还是用双指针法，先通过两个判断来把字符串前导空格和尾随空格都去掉，从而让 left 和 right 分别指向第一个和最后一个字母，方便我们遍历

  • 两个判断都需要 left <= right 作为先导条件，同时可以再用一个判断，如果 left > right 就直接返回空的字符串

  • 声明一个字符串类型的数组 words，进入一个循环

    • 循环内首先先判断当前 left 是否指向了空格，如果是的就移动 left 并 continue，保证 left 指向的是字母

    • 然后将 left 当前位置赋给一个新变量 start，再移动 left 直至下一个空格处，这样 start 到新的 left 就刚好是一个单词

    • 直接利用 append 和 切片将这个单词传入 words

• 其次我们需要再用一次常规的双指针法来反转 words，方便我们接下来组合

• 最后声明一个字符串 results，遍历一下 words，循环内先对当前索引是否大于零做一下判断，再利用 += 将单词赋给 results，这样就可以实现每次添加一个单词都会加一个空格的效果

这道题本质并不难，只是逻辑显得有点复杂，头脑清晰就可以轻松解决，只要注意字符串底层的索引是只读，所以通过索引拿是可以的，只是不能修改，然后对于 go 中常用的字符串操作要熟悉

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

题目：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

我的解答

这道题虽然是简单题，暴力法遍历起来时间复杂度也只是 O(n * m)，但如果是第一次接触 KMP 算法的话，会比较折磨，感觉这题其实就是用来学 KMP 算法的，详情可以见我的算法学习记录

459. 重复的子字符串

题目：https://leetcode.cn/problems/repeated-substring-pattern/description/

我的解答

这道题其实方法挺多的，可以直接暴力法枚举也可以将原本的字符串跟自身拼接一次，去头去尾之后再用 strings 标准包的 Contains 函数来查找中间是否有原串，这两个方法具体的就不仔细讲了，示例的话后续回来二刷三刷可能会写一下，这里我们还是主要专注于 KMP 算法，具体思路如下：

• 还是先构造一下 next 数组

  • 本质就是找子串的最长的相同前后缀，拿 abcabcabc 这个字符串举例

  • 我们要用双指针法，两个指针 i、j 一快一慢遍历这个字符串，一开始两个指针 j、i 分别指向 a 和 b，我们要对两个指针指向的字符进行比较是否相同，然后 ab 这个子串并没有相同前后缀对吧，也就是两个指针指向的字符不同，我们就 next[i] = j 赋值，然后快指针 i 到 c，慢指针 j 不动，发现 abc 这个子串还是没有，继续赋值

  • 但赋值本身是每次快指针走都会进行的，也就是说其实是如果两个指针指向的字符不同，我们是要让慢指针 j 回退的，也就是 j = next[j - 1]，回到上一个可能的最长相同前后缀

  • 然后到 abca，我们会发现这个子串的最长相同前后缀就是 a，也就是两个指针指向的字符相同了，所以慢指针要往前走一步，到 b，然后再赋值

  • 直到遍历完整个字符串，next 数组就构造好了

• 然后我们就进行一些巧妙的数学计算，首先我们可以观察到就是，abcabcabc 这个字符串，最长的相同前后缀长度是 6，我们把它取出来，然后用字符串长度减去它之后得到一个值，再用字符串长度取模这个值

  • 我们会发现只要能重复组成的话，next 数组的最后一个就肯定是最长的，然后取模之后肯定也会是 0，也就是说肯定会被整除，我们就这样判断

这道题算是 KMP 算法的另一种应用了，可以跟上一题结合着来看

以下为补充题，刷完代码随想录和 hot100 后会重新整理

844.比较含退格的字符串

题目：https://leetcode.cn/problems/backspace-string-compare/description/

我的解答，本题为简单题（但我感觉还是挺难的，毕竟第一次做字符串的题目👉👈）

这道题其实是属于字符串的相关题目了，所以做起来会比较陌生，毕竟还没做到这一块，之所以会有这道题是因为它被放在了代码随想录数组题目的相关题目推荐里面，于是也顺便一起做了，也是用双指针法，分析如下：

• 在不改变两个字符串的前提下， 我们可以考虑对两字符串分别的遍历（使用快慢指针，但这里其实是两个字符串各自的索引指针所形成的快慢）

• 并引入两个计数器变量，只要遇到退格符#就增加，以此来判断是对字符串的哪个元素进行比较

• 通过一个while循环（不知道具体遍历次数，不使用for）下嵌套两个while循环，内层循环的作用便是跳过所有需要被退格的字符，来完成含退格字符串的比较

• 如果遇到了退格符#，计数器增加，指针左移

• 如果计数器大于零，计数器减少，指针左移（相当于跳过了这个元素）

• 其他情况，跳出这个内层循环，该字符串本次筛选完毕

这题本质上考察的是对于双指针法的灵活使用，也就是另一种应用方式，一开始容易以为是要把退格符前面的元素和退格符一起删掉，然后再比较剩下的字符串是否相同，但这样操作一个是可能会造成访问越界，另一个是删除方式错误，这也是我第一个错误代码的问题

而如果只使用一个计数器变量，就容易造成我第二个错误代码的问题，这会导致在处理一个字符串的退格时，影响到另一个字符串的退格计数，而且我第二个错误代码的循环条件也大错特错

所以，正确的逻辑应该是，每次循环都分别对两个字符串进行一次筛选，找到可以比较的元素，进行比较，注意事项如下：

1. 要创建并维护两个计数器变量，因为两个字符串的长度可能是不同的
2. 循环条件一定要正确
3. 两个数组分开进行各自的筛选，逻辑清晰的同时不会造成混乱
4. 循环最后要将两个指针左移，因为每次外层循环都可以确定两个字符串中的元素是有被比较过的

关键还是在于能不能意识到不需要对字符串本身进行删改，只需要遍历即可