1. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：
输入：s = [“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]

示例 2：
输入：s = [“H”,“a”,“n”,“n”,“a”,“h”]
输出：[“h”,“a”,“n”,“n”,“a”,“H”]

# python
class Solution:def reverseString(self, s: List[str]) -> None:"""Do not return anything, modify s in-place instead."""left, right = 0, len(s) - 1while(left < right):s[left], s[right] = s[right], s[left]left += 1right -= 1

// Java
class Solution {public void reverseString(char[] s) {int left = 0, right = s.length - 1;while (left < right) {s[left] ^= s[right];s[right] ^= s[left];s[left] ^= s[right];left++;right--;}}
}

2. 反转字符串II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

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

示例 1：
输入：s = “abcdefg”, k = 2
输出：“bacdfeg”

示例 2：
输入：s = “abcd”, k = 2
输出：“bacd”

# python
class Solution:def reverseStr(self, s: str, k: int) -> str:def reverse_substring(text):left, right = 0, len(text) - 1while left < right:text[left], text[right] = text[right], text[left]left += 1right -= 1return textres = list(s)for i in range(0, len(s), 2 * k):res[i:i+k] = reverse_substring(res[i:i+k])	# python切片取出剩余的部分，不会报超出索引return ''.join(res)

# Java
class Solution {public String reverseStr(String s, int k) {char[] res = s.toCharArray();for (int i = 0; i < res.length; i += 2 * k) {if (i + k <= res.length) {reverse_substring(res, i, i + k - 1);} else {reverse_substring(res, i, res.length - 1);}}return new String(res);}public void reverse_substring(char[] text, int i, int j) {for (; i < j; i++, j--) {text[i] ^= text[j];text[j] ^= text[i];text[i] ^= text[j];}}
}

3. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：
输入：s = “We are happy.”
输出：“We%20are%20happy.”

# python
class Solution:def replaceSpace(self, s: str) -> str:counter = s.count(' ')res = list(s)res.extend([' '] * 2 * counter)left, right = len(s) - 1, len(res) - 1while left >= 0:if res[left] != ' ':res[right] = res[left]right -= 1else:res[right - 2 : right + 1] = '%20'right -= 3left -= 1return ''.join(res)

// Java
class Solution {public String replaceSpace(String s) {StringBuilder sb = new StringBuilder();for (int i = 0; i < s.length(); i++) {// str.charAt(i) 为 char 类型if (s.charAt(i) != ' ') {sb.append(s.charAt(i));} else {sb.append("%20");}}return sb.toString();}
}

4. 翻转字符串里的单词

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

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

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：
输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格。

示例 1：
输入：s = “the sky is blue”
输出：“blue is sky the”

示例 2：
输入：s = " hello world "
输出：“world hello”
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。

# pyhton
class Solution:def reverseWords(self, s: str) -> str:res = self.trim_space(s)self.reverse_string(res, 0, len(res) - 1)self.reverse_each_word(res)return ''.join(res)def trim_space(self, s): res = []left, right = 0, len(s) - 1while s[left] == ' ':  left += 1while s[right] == ' ':  right -= 1while left <= right:if s[left] != ' ':res.append(s[left])elif res[-1] != ' ':res.append(s[left])left += 1return resdef reverse_string(self, s, left, right):   # 使用是s[left:right+1]切片的方式无法对原数组进行翻转.while(left < right):s[left], s[right] = s[right], s[left]left += 1right -= 1return None def reverse_each_word(self, s):left, right = 0, 0while left < len(s):while right<len(s) and s[right] != ' ':right += 1self.reverse_string(s, left, right - 1)right += 1left = right

// Java
// 在Java中用StringBuilder来实现，如果按照python的思路，将字符串转成数组实现会提示内存超出限制。
class Solution {public String reverseWords(String s) {StringBuilder sb = removeSpace(s);reverseString(sb, 0, sb.length() - 1);reverseEachWord(sb);return sb.toString();}private StringBuilder removeSpace(String s) {int left = 0, right = s.length() - 1;while (s.charAt(left) == ' ') left++;while (s.charAt(right) == ' ') right--;StringBuilder sb = new StringBuilder();while (left <= right) {char c = s.charAt(left);if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {sb.append(c);}left++;}return sb;}private void reverseString(StringBuilder sb, int left, int right) {while (left < right) {char tmp = sb.charAt(left);sb.setCharAt(left, sb.charAt(right));sb.setCharAt(right, tmp);left++;right--;}}private void reverseEachWord(StringBuilder sb) {int left = 0, right = 0;while (left < sb.length()) {while (right < sb.length() && sb.charAt(right) != ' ') {right++;}reverseString(sb, left, right - 1);right++;left = right;}}
}

5. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：
输入: s = “abcdefg”, k = 2
输出: “cdefgab”

示例 2：
输入: s = “lrloseumgh”, k = 6
输出: “umghlrlose”

# python
class Solution:def reverseLeftWords(self, s: str, n: int) -> str:def reverse_sub (s, left, right):while left < right:s[left], s[right] = s[right], s[left]left += 1right -= 1res = list(s)reverse_sub(res, 0, n - 1)reverse_sub(res, n, len(res) - 1)reverse_sub(res, 0, len(res) - 1)return ''.join(res)

// Java
class Solution {public String reverseLeftWords(String s, int n) {StringBuilder sb = new StringBuilder(s);reverseString(sb, 0, n - 1);reverseString(sb, n, s.length() - 1);return sb.reverse().toString();}public void reverseString(StringBuilder sb, int left, int right) {while (left < right) {char tmp = sb.charAt(left);sb.setCharAt(left, sb.charAt(right));sb.setCharAt(right, tmp);left++;right--;}}
}

6. 实现strStr()

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：
输入：haystack = “hello”, needle = “ll”
输出：2

示例 2：
输入：haystack = “aaaaa”, needle = “bba”
输出：-1

示例 3：
输入：haystack = “”, needle = “”
输出：0

KMP算法：在一个串中查找是否出现过另一个串，可以使用KMP来降低复杂度。当出现不匹配的情况事，KMP不是从头开始匹配，而是利用前面已经匹配过的字符串来接着判断是否匹配。KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。B站视频讲解

# python
class Solution:def strStr(self, haystack: str, needle: str) -> int:if len(needle) == 0:return 0next = self.getNext(needle)j = 0for i in range(len(haystack)):while(j > 0 and needle[j] != haystack[i]):j = next[j - 1]if(needle[j] == haystack[i]):j += 1if(j == len(needle)):return i - j + 1return -1def getNext(self, s):# 1. 初始化 i为后缀末尾，j为前缀末尾j = 0next = ['' for i in range(len(s))]next[0] = 0for i in range(1, len(s)):	# i为后缀末尾，后缀不包括第一个字符，故i要从1开始# 2. s[i] != s[j]   回退while(j > 0 and s[i] != s[j]):j = next[j - 1]# 3. s[i] == s[j]   j++if(s[i] == s[j]):j += 1# 4. 更新next[]数组next[i] = jreturn next

// Java
class Solution {public int strStr(String haystack, String needle) {if (needle.length() == 0) {return 0;}int j = 0;int[] next = getNext(needle);for (int i = 0; i < haystack.length(); i++) {while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {j = next[j - 1];}if (haystack.charAt(i) == needle.charAt(j)) {j++;}if (j == needle.length()) {return i - j + 1;}}return -1;}public int[] getNext(String s) {int[] next = new int[s.length()];int j = 0;next[0] = 0;for (int i = 1; i < s.length(); i++) {while (j > 0 && s.charAt(i) != s.charAt(j)) {j = next[j - 1];}if (s.charAt(i) == s.charAt(j)) {j++;}next[i] = j;}return next;}
}

7. 重复的子字符串

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:
输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。

示例 2:
输入: “aba”
输出: False

示例 3:
输入: “abcabcabcabc”
输出: True
解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

如果数组长度len % (len - (next[len - 1] + 1)) == 0 ，则说明 (数组长度-最长相等前后缀的长度) 正好可以被 数组的长度整除，说明有该字符串有重复的子字符串。
数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
把next数组打印出来，看看next数组里的规律，有助于理解KMP算法。

# python
class Solution:def repeatedSubstringPattern(self, s: str) -> bool:next = self.getNext(s)if next[-1] != 0 and len(s) % (len(s) - next[-1]) == 0:return Trueelse:return Falsedef getNext(self, s):next = [0] * len(s)j = 0for i in range(1, len(s)):while j > 0 and s[i] != s[j]:j = next[j - 1]if s[i] == s[j]:j += 1next[i] = jreturn next

// Java
class Solution {public boolean repeatedSubstringPattern(String s) {int[] next = getNext(s);int len = s.length();if (next[len - 1] != 0 && len % (len - next[len - 1]) == 0) {return true;} else {return false;}}public int[] getNext(String s) {int[] next = new int[s.length()];int j = 0;for (int i = 1; i < s.length(); i++) {while (j > 0 && s.charAt(i) != s.charAt(j)) {j = next[j - 1];}if (s.charAt(i) == s.charAt(j)) {j++;}next[i] = j;}return next;}
}