Leetcode 字符串篇

Leetcode刷题记录——字符串篇

Leetcode344 反转字符串

Python代码如下：

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left = 0
        right = len(s) - 1
        while left < right:
            # s[left], s[right] = s[right], s[left]
            # Python 的一项语法糖，它可以在不借助临时变量的情况下直接交换两个变量的值
            temp = s[left]
            s[left] = s[right]
            s[right] = temp
            left += 1
            right -= 1

Leetcode541 反转字符串Ⅱ

每隔2k个字符，反转前k个，后k个不动

当循环结束时，判断剩余字符数量的区间，做不同的反转操作

Python代码如下：

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        length = len(s)
        i = 0
        res = []
        while i < length and i+2*k <= length:
            temp = s[i:i+k][::-1]
            res.append(temp)
            res.append(s[i+k:i+2*k])
            i = i + 2*k
        if length - i < k:
            temp = s[i:][::-1]
            res.append(temp)
        if length - i < 2*k and length - i >= k:
            temp = s[i:i+k][::-1]
            res.append(temp)
            res.append(s[i+k:])
        
        return ''.join(res)

Leetcode151 翻转字符串里的单词

首先用一个split函数分割字符串

再用双指针，同样的反转字符串的操作

最后用 ' '.join()合并就可以了

Python代码如下：

class Solution:
    def reverseWords(self, s: str) -> str:
        words = s.split()
        left = 0
        right = len(words) - 1
        while left < right:
            words[left], words[right] = words[right], words[left]
            left += 1
            right -= 1
        return ' '.join(words)

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

KMP思想

主要是求出根据子串求next数组

讲起来太抽象，可以看代码随想录

Python代码如下：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        next = [0] * len(needle)
        j = 0
        for i in range(1, len(needle)):
            while j > 0 and needle[i] != needle[j]:
                j = next[j-1]
            if needle[i] == needle[j]:
                j += 1
            next[i] = j
        
        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-j+1
        return -1
        

Leetcode459 重复的子字符串

如果这个字符串包含重复的子串

假设是字符串abcabc，记为s

那么s一定包含在s+s内

所以判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成

我们在判断 s + s拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s

还是回到了KMP算法

只不过这道题的模式串变成了(s+s)[1:-1]（拼接再去掉首位字符）

子串变成了s

Python代码如下：

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        next = [0] * len(s)
        j = 0
        needle = (s+s)[1:-1]
        for i in range(1, len(s)):
            while j > 0 and s[j] != s[i]:
                j = next[j-1]
            if s[j] == s[i]:
                j += 1
            next[i] = j
        
        j = 0
        needle = (s+s)[1:-1]
        for i in range(len(needle)):
            while j > 0 and needle[i] != s[j]:
                j = next[j-1]
            if needle[i] == s[j]:
                j += 1
            if j == len(s):
                return True
        return False