资料来源地址：代码随想录 (programmercarl.com)
这道题目可以说是综合考察了字符串的多种操作。
提高一下本题的难度：不要使用辅助空间，空间复杂度要求为O(1)。（Java不能在字符串上修改，所以使用java一定要开辟新空间）
解题思路如下：
- 移除多余空格
- 将整个字符串反转
- 将每个单词反转
举个例子，源字符串为："the sky is blue "
- 移除多余空格 : "the sky is blue"
- 字符串反转："eulb si yks eht"
- 单词反转："blue is sky the"
class Solution {
/**
* 不使用Java内置方法实现
* <p>
* 1.去除首尾以及中间多余空格
* 2.反转整个字符串
* 3.反转各个单词
*/
public String reverseWords(String s) {
// System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
// 1.去除首尾以及中间多余空格
StringBuilder sb = removeSpace(s);
// 2.反转整个字符串
reverseString(sb, 0, sb.length() - 1);
// 3.反转各个单词
reverseEachWord(sb);
return sb.toString();
}
private StringBuilder removeSpace(String s) {
// System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
int start = 0;
int end = s.length() - 1;
while (s.charAt(start) == ' ') start++;
while (s.charAt(end) == ' ') end--;
StringBuilder sb = new StringBuilder();
while (start <= end) {
char c = s.charAt(start);
if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
start++;
}
// System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
return sb;
}
/**
* 反转字符串指定区间[start, end]的字符
*/
public void reverseString(StringBuilder sb, int start, int end) {
// System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
// System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
}
private void reverseEachWord(StringBuilder sb) {
int start = 0;
int end = 1;
int n = sb.length();
while (start < n) {
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
}提升一下本题难度：不能申请额外空间，只能在本串上操作。 （Java不能在字符串上修改，所以使用java一定要开辟新空间）
思路就是 通过 整体倒叙，把两段子串顺序颠倒，两个段子串里的的字符在倒叙一把，负负得正，这样就不影响子串里面字符的顺序了。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = Integer.parseInt(in.nextLine());
String s = in.nextLine();
int len = s.length(); //获取字符串长度
char[] chars = s.toCharArray();
reverseString(chars, 0, len - 1); //反转整个字符串
reverseString(chars, 0, n - 1); //反转前一段字符串，此时的字符串首尾尾是0,n - 1
reverseString(chars, n, len - 1); //反转后一段字符串，此时的字符串首尾尾是n,len - 1
System.out.println(chars);
}
public static void reverseString(char[] ch, int start, int end) {
//异或法反转字符串，参照题目 344.反转字符串的解释
while (start < end) {
ch[start] ^= ch[end];
ch[end] ^= ch[start];
ch[start] ^= ch[end];
start++;
end--;
}
}
}KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。
- 什么是KMP
- KMP有什么用
- 什么是前缀表
- 为什么一定要用前缀表
- 如何计算前缀表
- 前缀表与next数组
- 使用next数组来匹配
- 时间复杂度分析
- 构造next数组
- 使用next数组来做匹配
- 前缀表统一减一 C++代码实现
- 前缀表（不减一）C++实现
- 总结
class Solution {
public int strStr(String haystack, String needle) {
int hLen = haystack.length(), nLen = needle.length();
if (hLen < nLen) {
return -1;
}
if (nLen == 0) {
return 0;
}
int[] next = new int[nLen];
for (int i = 1, j = 0; i < nLen; i++) {
while ((j > 0) && (needle.charAt(i) != needle.charAt(j))) {
j = next[j - 1];
}
if (needle.charAt(i) == needle.charAt(j)) {
j++;
}
next[i] = j;
}
for (int i = 0, j = 0; i < hLen; i++) {
while ((j > 0) && (needle.charAt(j) != haystack.charAt(i))) {
j = next[j - 1];
}
if (needle.charAt(j) == haystack.charAt(i)) {
j++;
}
if (j == nLen) {
return (i - nLen + 1);
}
}
return -1;
}
}如果这个字符串s是由重复子串组成，那么最长相等前后缀不包含的子串是字符串s的最小重复子串。
如果字符串s的最长相等前后缀不包含的子串 是 s最小重复子串，那么 s是由重复子串组成。
强烈建议大家把next数组打印出来，看看next数组里的规律，有助于理解KMP算法
class Solution {
public boolean repeatedSubstringPattern(String s) {
if (s.equals("")) return false;
int len = s.length();
// 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
s = " " + s;
char[] chars = s.toCharArray();
int[] next = new int[len + 1];
// 构造 next 数组过程，j从0开始(空格)，i从2开始
for (int i = 2, j = 0; i <= len; i++) {
// 匹配不成功，j回到前一位置 next 数组所对应的值
while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
// 匹配成功，j往后移
if (chars[i] == chars[j + 1]) j++;
// 更新 next 数组的值
next[i] = j;
}
// 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
if (next[len] > 0 && len % (len - next[len]) == 0) {
return true;
}
return false;
}
}字符串类类型的题目，往往想法比较简单，但是实现起来并不容易，复杂的字符串题目非常考验对代码的掌控能力。
双指针法是字符串处理的常客。
KMP算法是字符串查找最重要的算法，但彻底理解KMP并不容易。