344. Reverse String

这题自己做对了，还有更精简的方法：

使用reversed，s[:] = reversed(s)

使用切片，s[:] = s[::-1]

使用reverse(), s.reverse()

541. Reverse String II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def reverseStr(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        s_list = [ss for ss in s]

        if k >= len(s_list):
            s_list.reverse()
            res = "".join(s_list)
            return res 

        k_l, k_r = 0, k

        while k_r <= len(s_list):

            k_reverse = s_list[k_l:k_r]
            k_reverse.reverse()
            s_list[k_l:k_r] = k_reverse
            k_l += k*2
            k_r += k*2

        res = "".join(s_list)
        return res

我写的代码有两个错误，一个是while循环的条件错了，应该是k_l < len(s_list)，因为如果用k_r的话那么k_l到结尾距离要是小于2k但是大于k的时候不会被处理。

第二个是k_r += k*2可能出现越界的问题，因此需要取最小值k_r = min(len(s_list),k_l + k),使用k_l+k就能描述 k_r += k*2.

另外，还可以优化代码，比如

1
2
3
4
5
6
7
8
9
10
11
12
s_list = [ss for ss in s] ---> s_list = list(s)

k_reverse = s_list[k_l:k_r]
k_reverse.reverse()
s_list[k_l:k_r] = k_reverse
可以优化成
s_list[k_l:k_r] = reversed(s_list[k_l:k_r] )
或者更加简便的写法，思路是将2k看作一个区间，然后用for跳着遍历，在每个区间内只反转前k个字符

for i in range(0, len(s_list), 2 * k):  # 每 2k 作为一个区间
        s_list[i:i + k] = reversed(s_list[i:i + k])  # 仅反转前 k 个字符

自动处理边界，不会越界，最后一个区间小于 k 仍然会被反转，如果最后一个区间小于 2k 但大于 k，后 k 个字符保持不变

151. Reverse Words in a String

这题注意：

1
s_list = [x for x in s_list if x!=""] # 这里的x!=""而不是x!=" "

这是因为s.split(" ") 按单个空格拆分，多个空格会产生 "" 需要手动去除 ""，

而s.split() 按空格拆分，自动去掉多余空格

如果不用split，那可以按传统方法， 分三步

首先去重，然后双指针将所有字符反转，然后再按空格将每个单词反转(整体反转+局部反转)

1
2
3
4
5
6
7
8
9
10
11
12
13
def reverseWords(self, s: str) -> str:
        # 将字符串拆分为单词，即转换成列表类型
        words = s.split()

        # 反转单词
        left, right = 0, len(words) - 1
        while left < right:
            words[left], words[right] = words[right], words[left]
            left += 1
            right -= 1

        # 将列表转换成字符串
        return " ".join(words)

28. Find the Index of the First Occurrence in a String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def getNext(self, next: List[int], s: str) -> None:
        j = 0
        next[0] = 0
        for i in range(1, len(s)):
            while j > 0 and s[i] != s[j]:
                j = next[j - 1]
            if s[i] == s[j]:
                j += 1
            next[i] = j

    def strStr(self, haystack: str, needle: str) -> int:
        if len(needle) == 0:
            return 0
        next = [0] * len(needle)
        self.getNext(next, needle)
        j = 0
        for i in range(len(haystack)):
            while j > 0 and haystack[i] != needle[j]:
                j = next[j - 1]
            if haystack[i] == needle[j]:
                j += 1
            if j == len(needle):
                return i - len(needle) + 1
        return -1

KMP算法，主要用来匹配子字符串，复杂度m+n，关键思想就是给要匹配的字符串创建一个next数组，用来告诉主指针如果指到没匹配上的位置的时候该从哪个位置开始匹配，而不是从头再来

B站KMP算法中印度老哥讲的最好。主要思想是将要匹配的字符串和主字符串一一比对，如果匹配不上 的话，就在当前位置回头看有没有相同的子序列，比如：

主字符串：abcab x abcab c aby

要匹配的：abcab y

首先将下面和上面比对，直到y这个位置发现匹配不上了，于是就寻找y前面有没有相同的两个或以上的子序列，发现有，也就是ab，那就说明在x和y的前一个都是ab，所以下一次比对开始只要从 y 前面的ab再前面的ab的后一个位置（这里是c）开始比对就行了，

而主序列也从x开始比对，也就是说首先比对x和c，发现不相等，所以下面的序列从c开始再次往前找有没有两个或者以上的相同子序列，发现前面都是独立的元素并没有子序列，因此就需要从头开始比对，而主序列则继续从x开始比对，

从x开始后一直到主序列的c和下面序列的y再次比对不上了，这个时候下面序列再次从y往前找有没有相同的子序列，发现还是ab，于是就找到y前面ab的再前面的ab的后面的位置（c）开始继续比对，这次发现主序列也是c，比对上了，那么下面的序列就可以从c开始比对而不是从头开始比对，主序列也是从c开始，直到结束，最后比对成功，返回主序列第一次比对上的下标。

那么怎么向前找是否有相同的子序列呢，这里定义一个next数组用于存放位置，用两个指针i和j分别指向主序列的开头和第二个位置，其中i用于在前面比对，j用于与i相比较，是否相等。如果相等的话，j的位置的数组值就加1，然后分别往下移动一个位置，然后继续判断第二个位置是否相等，如果再相等的话那j这个位置的值比刚才记录的第一个相等的位置的值再加1也就是2，如果再下一个位置不相等，那就j回到其前一个值所对应的next数组里的位置，这里建议看视频7:40处容易理解。

或者用双指针，也就是两个指针分别比对是否相等，相等就都++，不相等那要配对的序列的指针就回到初始位置，最后一次会迭代到needle末尾，也就是p2==n2，如果是的话说明比对上了 ，返回p1-p2的差值为开始的下标

459. Repeated Substring Pattern

这题有几种做法，最有技巧性和直观的是字符串拼接法（最优解，O(N)）

核心思想：如果 s 可以由子串 t 重复构成，那么：s + s 去掉首尾字符后，仍然包含 s。

1
2
3
4
s = "abab"
s + s = "abababab"
去掉头尾: "bababa"
发现仍然包含 "abab"

所以只需要判断s+s去掉首尾后是否包含s即可，一句话return s in (s+s)[1:-1]

或者KMP 前缀表算法，利用 KMP 算法的 next 数组，找到 s 的最长相同前后缀。

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

记 next[-1] = L（最后一个 next 值）。如果 L > 0 且 s 的长度 len(s) % (len(s) - L) == 0，说明 s 是某个子串的重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def repeatedSubstringPattern(s):
    def compute_next(s):
            next_arr = [0] * len(s)  # 初始化 next 数组
            j = 0  # 记录前缀匹配长度

            for i in range(1, len(s)):  # 从索引 1 开始
                    while j > 0 and s[i] != s[j]:  # 失配时回退
                            j = next_arr[j - 1]  

                    if s[i] == s[j]:  # 匹配成功，增加匹配长度
                            j += 1

                    next_arr[i] = j  # 记录前缀匹配值

            return next_arr

    next_arr = compute_next(s)
    L = next_arr[-1]
    return L > 0 and len(s) % (len(s) - L) == 0

这里 next_arr 只用于判断 L 是否能整除 len(s)