# 二刷力扣--字符串

## 字符串

### 344.反转字符串

#双指针

class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
n = len(s)
for i in range(n // 2):
s[i], s[n - i - 1] = s[n - i - 1], s[i]


python中最简单的反转是用 [::-1]

### 541. 反转字符串 II

#模拟

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

class Solution:
def reverseStr(self, s: str, k: int) -> str:
right = 2*k
n = len(s)
res = ""
while right <= n:
res += s[right-2*k:right-k][::-1] + s[right-k:right]
right += 2*k
right -= 2*k
if n - len(res) < k:
res += s[right:][::-1]
elif n-len(res)>= k:
res += s[right:right+k][::-1] + s[right+k:]

return res


class Solution:
def reverseStr(self, s: str, k: int) -> str:
p = 0
while p < len(s):
p2 = p + k
s = s[:p] + s[p: p2][::-1] + s[p2:]
p = p + 2 * k
return s


### 剑指 Offer 05. 替换空格

class Solution:
def replaceSpace(self, s: str) -> str:
res = ""
for c in s:
if c == " ":
res += "%20"
else:
res += c
return res


### 151. 反转字符串中的单词

class Solution:
def reverseWords(self, s: str) -> str:
s = [x  for x in s.split(" ") if x != '']
return " ".join(s[::-1])


### 剑指 Offer 58 - II. 左旋转字符串

class Solution:
def reverseLeftWords(self, s: str, n: int) -> str:
s = s[n:] + s[:n]
return s


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

class Solution:
def strStr(self, haystack: str, needle: str) -> int:
n = len(haystack)
left = 0
right = len(needle)
if right == 0:
return 0
while right <= n:
if haystack[left: right] == needle:
return left
left += 1
right += 1
return -1



KMP算法名字由发明它的三个人的名字组成，解决字符串的匹配问题。

s：aabaabaaf

t：aabaaf

class Solution:
def getNext(s):
next = [0] * len(s)
j = 0  # j代表前缀末尾
next[j] = 0
for i in range(1,len(s)): # i代表后缀末尾
while j > 0 and s[i] != s[j]:# 不等时回退j
j = next[j-1]
if s[i] == s[j]: # 相等时， j+1
j += 1
next[i] = j
return next

def strStr(self, haystack: str, needle: str) -> int:
if len(needle) == 0:
return 0
next = Solution.getNext(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


getNext的j=next[j-1]那里不是特别明白，但是背下来了。

next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度

### 重复的子字符串

1. 暴力
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
n = len(s)
if n <= 1:
return False

substr = ""
for i in range(1, n//2 + 1):
if n % i == 0:
substr = s[:i]
if substr * (n//i) == s:
return True

return False

1. find
如果s由重复子串组成，那么两个s拼接在一起，中间肯定会再出现一个s。
(当然这只说明了必要性，还要证明充分性。)
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
n = len(s)
if n <= 1:
return False
ss = s[1:] + s[:-1]
return ss.find(s) != -1
`

|
16天前
|

11 1
|
16天前

10 1
|
29天前
|

18 3
|
29天前
|

10 1
|
29天前

12 1
|
29天前

12 1
|
29天前
|

11 1
|
29天前
|
Java Python

15 1
|
29天前
|
C++ Python

14 1
|
16天前
|

8 0