LeetCodeCampsDay9

字符串反转

151. 反转字符串中的单词

https://leetcode.cn/problems/reverse-words-in-a-string/

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

1
2
输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

1
2
3
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

1
2
3
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

  • 1 <= s.length <= 104
  • s 包含英文大小写字母、数字和空格 ' '
  • s 中 至少存在一个 单词

**进阶：**如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法

思路

  1. 先去年多余的空格，可以使用快慢指针思路，当快指针遇到字符时，先给slow添加个空格，当作每两个单词之间的空格（当然slow不能为0）；再同时推进slow与fast，将fast指向的单词转移到slow的位置
  2. 再将整体反转
  3. 最后，将每个单词反转for i in range(L + 1): if i == L or s[i] == " ": 这里需要注意跳出的条件，因为有时最后一个词也需要反转，但最后一个词后面是没有空格的，所以需要将i的范围从0到L都遍历一遍，并且遇到i==L时，再做一次反转（特殊情况）

代码

  • 时间复杂度O(N)
  • 空间复杂度O(1)
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def reverseClip(self, s:list) -> list:
        L = len(s)
        for i in range(L//2):
            s[i], s[L - i -1] = s[L - i - 1], s[i]
        
        return s
    
    def removeSpace(self, s: list) -> list:
        L = len(s)
        slow = 0
        i = 0
        while i < L:
            if s[i] != ' ':
                if slow != 0:
                    s[slow] = " "
                    slow += 1
                while i < L and s[i] != " ":
                    s[slow] = s[i]
                    slow += 1
                    i += 1
            i += 1
        return s[:slow]

    def reverseWords(self, s: str) -> str:
        s = list(s)
        # 先删除空格
        s = self.removeSpace(s)
        # 先反转整体，再局部反转
        s = self.reverseClip(s)
        L = len(s)
        leftIndex = 0
        
        for i in range(L + 1):
            if i == L or s[i] == " ":
                s[leftIndex: i] = self.reverseClip(s[leftIndex: i])
                leftIndex = i + 1

        return "".join(s)

右旋字符串（第八期模拟笔试）

题目描述

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。

输入描述

输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

输出描述

输出共一行，为进行了右旋转操作后的字符串。

输入示例

1
2
2
abcdefg

输出示例

1
fgabcde

提示信息

数据范围：
1 <= k < 10000,
1 <= s.length < 10000;

思路

  1. 将整体反转
  2. 再将前k个反转，以及剩下的L-k个反转

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class solution():
    def reverseClip(self, s: list) -> list:
        L = len(s)
        for i in range(L//2):
            s[i], s[L - i - 1] = s[L - i - 1], s[i]
        return s

    def reverseR(self, k: int, s: str) -> str:
        s = list(s)
        s = self.reverseClip(s)
        s[0:k] = self.reverseClip(s[0:k])
        s[k:] = self.reverseClip(s[k:])
        
        return "".join(s)

k = int(input())
s = input()
solu = solution()
res = solu.reverseR(k, s)
print(res)

KMP算法

核心是求“子串的最长相等前后缀”

比如"aabaaf"，对f来说，它的子串（即aabaa）的最长相等前后缀是"aa"

前缀不包含最后一个尾字母，后缀不包含首字母

kmp学了忘，忘记再学，哎，之前都没理解深刻，这次发现了一个很有意思的两个重点

  1. left指针是个重点，它是“已经匹配上的前缀的长度”，而且它不是单调变化的
  2. kmp每次将前n个字符与后n个字符进行匹配，并且n逐个减一地再进行循环匹配，完美解决了“最长前后缀”的匹配问题

KMP思路

  1. KMP的核心思路是找“子串的最长相等前后缀”（所谓的前缀表，即，prefix或next数组）
  2. 比如aabaa的最长相等前后缀是"aa"，aabaaf的最长相等前后缀是""，aabaafa的最长相等前后缀是"a"
  3. 可以使用双指针思路来找"最长相等前后缀"
  4. 将数组一分为二，比如aa|baaf，其中aa为前缀子串；baaf为后缀子串
  5. left指针：指向已匹配上的前缀的长度，left是非单向的，它初始化为0->1->0->1->2->1，只有当s[left]==s[right]时才递增；否则就会下降
  6. right指针：指向后缀最后一个位置, right是单向递增的，它只会从1->2->3…->n
下标 0 1 2 3 4 5 6
串 a a b a a b f
前缀表(next数组) 0 1 0 1 2 3 0

举例求"aabaa"的next数组

初始化left=0;next数组全为0；right=1

下标 0 1 2 3 4
串 a a b a a
前缀表(next数组) 0 0 0 0 0
变量位置 left right

s[left]==s[right]，说明找到了一对最长前后缀"aa"

left更新：left=left+1即下标1（此时需要指向right的位置），left维护的是0~1这个子串里最长前缀的下标

并更新next数组，next[right]=left，更新了下标1位置的next数组，说明长度为1的前缀与**‘a’(1)匹配**

下标 0 1 2 3 4
串 a a b a a
前缀表(next数组) 0 1 0 0 0
变量位置 left right

While…

  • s[left]!=s[right](s[1]!=s[2])，说明’aa’是无法与’b’匹配的
  • Left更新left = next[left-1],即left=0
  • 然后s[left]再与s[right]判断，此时s[left]!=s[right]，再想更新left = next[left-1]，但此时left已经为0，无法更新，因为越界了，所以需要添加个判断条件left>0时才能更新left（这一步是在一个while执行的）

If…

  • s[left]!=s[right](s[0]!=s[2])，说明’a’无法与’b’匹配

next[right] = left；更新了下标2位置的next数组，说明长度为0的前缀与**'b’匹配**

最后，right更新，指向下标3

下标 0 1 2 3 4
串 a a b a a
前缀表(next数组) 0 1 0 0 0
变量位置 left right

While…

  • s[left]==s[right](s[0]==s[3])，说明’a’(0)是与’a’(3)匹配的，退出while

If…

  • s[left]==s[right](s[0]==s[3])，说明’a’(0)是与’a’(3)匹配的
  • left += 1, # left = 1

next[right] = left；更新了下标3位置的next数组，说明长度为1的前缀与**‘a’(3)匹配**

最后，right更新，指向下标4

下标 0 1 2 3 4
串 a a b a a
前缀表(next数组) 0 1 0 1 0
变量位置 left right

While…

  • s[left]==s[right](s[1]==s[4])，说明’aa’(0,1)是与’aa’(3,4)匹配的，退出while

If…

  • s[left]==s[right](s[1]==s[4])，说明’aa’(0,1)是与’aa’(3,4)匹配的
  • left += 1, # left = 2

next[right] = left；更新了下标4位置的next数组，说明长度为2的前缀与**‘aa’(3,4)匹配**

最后，right更新，指向下标5

下标 0 1 2 3 4 5
串 a a b a a f
前缀表(next数组) 0 1 0 1 2 0
变量位置 left right

While…

注意，这里虽然只比较了s[left]!=s[right](s[2]!=s[5])，但它实际比较的是**‘aab’(0,1,2)是与’aaf’(3,4,5)不匹配的**，因为**‘aa’(0,1)是与’aa’(3,4)匹配是已知的信息**，只有将s[2]与s[5]判断，就能直接知道这s(0~2)与s(3~5)是否一样了

  • s[left]!=s[right](s[2]!=s[5])，说明’aab’(0,1,2)是与’aaf’(3,4,5)不匹配的，于是退而求其次
  • left = next[left - 1] # left = 1
  • s[left]==s[right](s[1]==s[5])，说明’aa’(0,1)是与’af’(4,5)不匹配的，于是退而求其次
  • left = next[left - 1] # left = 0
  • s[left]==s[right](s[0]==s[5])，说明’a’(0)是与’f’(5)不匹配的，没得退了，此时left=0

If…

  • s[left]!=s[right](s[0]==s[5])，说明’a’(0)是与’f’(5)不匹配的，if不操作

next[right] = left；更新了下标4位置的next数组，说明长度为0的前缀与**‘f’(5)匹配**

最后，right更新，指向下标6

下标 0 1 2 3 4 5 6
串 a a b a a f a
前缀表(next数组) 0 1 0 1 2 0 0
变量位置 left right

img

KMP一个很神奇的一点是，它每次将前n个字符与后n个字符进行匹配，并且n逐个减一地再进行循环匹配，比如

’aab’(0,1,2)是与’aaf’(3,4,5)不匹配的

然后会比较

’aa’(0,1)是与’af’(4,5)不匹配的，

然后再比较

’a’(0)是与’f’(5)不匹配的

很完美地完成了“最长前后缀”问题

怎么理解left指针是已匹配上的前缀的长度呢

left代表当前子串 s[0...right] 的“最长相等前后缀”的长度。

left同时也是指向“最长前缀”的下一个字符的下标。

  • 当 left 为 0 时，我们比较 s[0] 和 s[right]。
  • 当 left 为 1 时，意味着前缀 s[0] 已经匹配上了，我们接下来要比较 s[1] 和 s[right]。
  • 当 left 为 k 时，意味着前缀 s[0...k-1] 已经匹配上了，我们接下来要比较 s[k] 和 s[right]。

KMP代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def getNext(self, s: str) -> list:
        # 函数返回s的最大相等前缀的数值结果表
        L = len(s)
        nextArry = [0] * L
        left = 0 # “已匹配上的前缀的长度”（很关键的一句话，如果能解理就能明白KMP算法了）
        nextIndex = 0
        for right in range(1, L):
            # 这里有个假设，next表是已经打造好的东西（或者是一边打造一边就要用）
            # 当s[left] != s[right]，让right向前搜索，令right = next[right - 1];
            # 很关键的思想，有点儿递归的意思
            while s[left] != s[right] and left > 0:
                left = nextArry[left]
            # 当s[left]等于s[right]说明找到了一组相等的前后缀
            if s[left] == s[right]:
                # 前缀指针向后移动
                left += 1
            # 更新next数组，这里的right即是next的下标，也是后缀的下标
            # 当然可以将nextIndex与right分开；这样更明确一点儿
            nextArry[nextIndex] = left
            nextIndex += 1
        return nextArry

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

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

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

1
2
3
4
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

1
2
3
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

  • 1 <= haystack.length, needle.length <= 104
  • haystack 和 needle 仅由小写英文字符组成

思路

  1. 先求next数组；再进行匹配，不过求next数组的代码和匹配字符串时的代码是一样的

代码

  • 时间复杂度O(N+M), 其中N为haystack长度，M是needle长度
  • 空间复杂度O(M)
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
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
    def getNext(self, s: str) -> list:
        # 函数返回s的最大相等前缀的数值结果表
        L = len(s)
        nextArry = [0] * L
        left = 0 # “当前子串中的最长前缀的下标”（很关键的一句话，如果能解理就能明白KMP算法了）
        nextIndex = 0
        for right in range(1, L):
            # 这里有个假设，next表是已经打造好的东西（或者是一边打造一边就要用）
            # 当s[left] != s[right]，让right向前搜索，令right = next[right - 1];
            # 很关键的思想，有点儿递归的意思
            while s[left] != s[right] and left > 0:
                left = nextArry[left - 1]
            # 当s[left]等于s[right]说明找到了一组相等的前后缀
            if s[left] == s[right]:
                # 前缀指针向后移动
                left += 1
            # 更新next数组，这里的right即是next的下标，也是后缀的下标
            # 当然可以将nextIndex与right分开；这样更明确一点儿
            nextArry[right] = left
            # nextIndex += 1
        return nextArry
        

    def strStr(self, haystack: str, needle: str) -> int:
        nextArry = self.getNext(needle)
        L = len(needle)
        L_hay = len(haystack)
        left = 0
        for i in range( L_hay):
            while left > 0 and haystack[i] != needle[left]:
                left = nextArry[left - 1]
            if needle[left] == haystack[i]:
                left += 1
            # 唯独需要在这儿判断是否到了needle的尾部
            if left == L:
                return i - L + 1

        return -1

459. 重复的子字符串

https://leetcode.cn/problems/repeated-substring-pattern/

示例 1:

1
2
3
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

1
2
输入: s = "aba"
输出: false

示例 3:

1
2
3
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

  • 1 <= s.length <= 104
  • s 由小写英文字母组成

代码

  • 时间复杂度(N)
  • 空间复杂度(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def getNext(self, s: str) -> list:
        L = len(s)
        nextArray = [0] * L
        left = 0
        for right in range(1, L):
            while s[left]!=s[right] and left > 0:
                left = nextArray[left - 1]
            if s[left]==s[right]:
                left += 1
            nextArray[right] = left
        return nextArray

    def repeatedSubstringPattern(self, s: str) -> bool:
        L = len(s)
        if L == 0:
            return False
        nextArray = self.getNext(s)
        if nextArray[-1]!=0 and L % (L - nextArray[-1]) == 0:
            return True
        return False