344. 反转字符串
??编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例一：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例二：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
思路：双指针。
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
i = 0
j = len(s) - 1
while i < j :
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
541. 反转字符串 II
??给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于
k个，则将剩余字符全部反转。 - 如果剩余字符小于
2k但大于或等于k个，则反转前k个字符，其余字符保持原样。
示例一：
输入：s = "abcdefg", k = 2
输出："bacdfeg"
示例二：
输入：s = "abcd", k = 2
输出："bacd"
思路：我们直接按题意进行模拟：反转每个下标从 2k 的倍数开始的，长度为 k 的子串。若该子串长度不足 k，则反转整个子串。
class Solution:
def reverseStr(self, s: str, k: int) -> str:
s = list(s)
for i in range(0, len(s), 2 * k) :
s[i : i + k] = s[i : i + k][ : : -1]
return "".join(s)
剑指 Offer 05. 替换空格
??请实现一个函数，把字符串 s 中的每个空格替换成 "%20"。
示例一：
输入：s = "We are happy."
输出："We%20are%20happy."
思路：一次遍历直接替换。
class Solution:
def replaceSpace(self, s: str) -> str:
s = list(s)
for i in range(len(s)) :
if s[i] == ' ' :
s[i] = '%20'
return "".join(s)
151. 颠倒字符串中的单词
??给你一个字符串 s ，颠倒字符串中 单词 的顺序。单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。注意：输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例一：
输入：s = "the sky is blue"
输出："blue is sky the"
示例二：
输入：s = " hello world "
输出："world hello"
解释：颠倒后的字符串中不能存在前导空格和尾随空格。
示例三：
输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，颠倒后的字符串需要将单词间的空格减少到仅有一个。
思路：双指针+反向遍历。
class Solution:
def reverseWords(self, s: str) -> str:
# 1、当快指针和慢指针同时指向空格时 fast 和 slow 都减一
# 2、当慢指针遇到一个单词的额末尾字母时，停下
# 3、当快指针遇到空格且慢指针不为空格的话，添加单词，这里要注意当 fast==0 时要另外处理
words = []
slow = len(s) - 1
for fast in range(len(s) - 1, -1, -1) :
if s[fast] != ' ' :
if fast == 0 :
words.append(s[fast : slow + 1])
else :
continue
else :
if s[slow] != ' ' :
words.append(s[fast + 1 : slow + 1])
slow = fast
slow -= 1
return " ".join(words)
459. 重复的子字符串
??给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例一：
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
示例二：
输入: s = "aba"
输出: false
示例三：
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
思路：这道题有很多钟方法，这里介绍字符串匹配。假设 s 由 n 个重复的子字符串 s' 构成，若 n == 1 则不满足要求，若 n >= 2，则满足题目要求。然后我们将第一个 s' 移到最后面，此时的字符串还是跟原始的 s 一样。然后我们将 s 扩展成 s + s，并且去除 s + s 的第一个字符和最后一个字符，相当于损坏了第一个 s 的第一个子字符串和第二个 s 的最后一个子字符串，如果在去除字符之后的字符串中我们还能找到原始的字符串 s，说明 s 满足条件。其实这里就相当于 n >= 2，然后第二个 s 的第一个子字符串填补了第一个 s 的最后一子字符串。这两个是充要条件。
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
return s in (s + s)[1 : len(s) * 2 - 1]
