字符串算法学习
字符串的操作主要涉及到String，char[]，StringBuilder，StringBuffer四种，值得注意的是，Java中String是无法被修改的，所以做题的时候往往涉及到这几种类型的转换，需要熟悉不同类型的操作方法。
字符串操作常用方法：
- toCharArray(String)：可以将String类转换为char数组。
- String(char[], left, right)：可以将char数组转换为String类型，同时还可以添加上参数来获取指定左右边界的String类。
- charAt(int)：可以获取String指定位置的字符。
- isDigit(char)：可以判断字符是否为数组。
- System.arraycopy(char[], int index, char[], int index, int size)：可以实现数组的拷贝。
- StringBuilder.append(char ch)：可以在StringBuilder末尾加入新字符。
- StringBuilder.toString()：可以将StringBuilder类转换为String类。
- StringBuilder.setCharAt(int index, char val)：可以在指定位置设置字符。
字符串基础
反转字符串
问题：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。
比较简单，不需要赘述什么，后面很多题目都需要用到字符串反转，有的是指定范围的反转。
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public void reverseString(char[] s) {
int l = 0;
int r = s.length - 1;
while(l < r){
char temp = s[l];
s[l] = s[r];
s[r] = temp;
l++;
r--;
}
}
}
反转字符串II
问题：给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。如果剩余字符少于 k 个，则将剩余字符全部反转，如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
模拟题，不需要多说，要熟悉String类的一些方法，将字符串转为数组才好做。
代码示例：
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
// 解法3
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
// 1. 每隔 2k 个字符的前 k 个字符进行反转
for (int i = 0; i< ch.length; i += 2 * k) {
// 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
if (i + k <= ch.length) {
reverse(ch, i, i + k -1);
continue;
}
// 3. 剩余字符少于 k 个，则将剩余字符全部反转
reverse(ch, i, ch.length - 1);
}
return new String(ch);
}
// 定义翻转函数
public void reverse(char[] ch, int i, int j) {
for (; i < j; i++, j--) {
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
}
}
双指针
替换数字
问题：给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。
这里的做法是先扫描字符串有多少个数字，将字符串大小扩大到替换为number后的大小，再从后进行填充。具体做法采用双指针法，i指向新长度的末尾，j指向旧长度的末尾，i向前遍历，遇到字母，则赋值给j所在的位置，j向前移动，遇到数字则开始填充number。
很多填充类问题都是采用这种方法，需要活学活用。
二刷思考：对字符串的一些方法还是不太熟悉，打算整理一下目前刷到的题中遇到的所有可以用得上的库方法，此外就是对循环的终止条件控制的不是很好，比如最开始采用left > 0 && right > 0出现了奇奇怪怪的bug，改用>=可解决。
代码示例：
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
import java.util.*;
import java.lang.*;
public class Main{
public static String Replace(String s){
int count = 0;
int oldSize = s.length();
for (int i = 0; i < s.length(); i++)
if(Character.isDigit(s.charAt(i)))
count++;
int newSize = oldSize + 5 * count;
char[] res = new char[newSize];
System.arraycopy(s.toCharArray(), 0, res, 0, oldSize);
int left = oldSize - 1;
int right = newSize - 1;
for(; left < right; left--, right--){
if(!Character.isDigit(res[left]))
res[right] = res[left];
else{
res[right] = 'r';
res[right - 1] = 'e';
res[right - 2] = 'b';
res[right - 3] = 'm';
res[right - 4] = 'u';
res[right - 5] = 'n';
right -= 5;
}
}
return new String(res);
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
System.out.println(Replace(s));
}
}
连续翻转
翻转字符串里的单词
问题：给你一个字符串s，请你反转字符串中单词的顺序。单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开，返回单词顺序颠倒且单词之间用单个空格连接的结果字符串，即输入：” hello world “ 输出：”world hello”。
综合考察了字符串的操作方法。先将整个字符串翻转，再对每个单词进行翻转，需要注意的是，要先去除原字符串中多余的空格，对于每个单词进行翻转，可以通过空格来判断各个单词的区间，调用字符串翻转方法即可。
二刷心得：仍然是边界情况的处理不够好，思路在线，但却debug了很久。二刷的时候采用的是对char数组进行操作的方式，意在练习各种对字符串进行操作的方法。
代码示例：
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
/**
* 不使用Java内置方法实现
* <p>
* 1.去除首尾以及中间多余空格
* 2.反转整个字符串
* 3.反转各个单词
*/
public String reverseWords(String s) {
// 1.去除首尾以及中间多余空格
StringBuilder sb = removeSpace(s);
// 2.反转整个字符串
reverseString(sb, 0, sb.length() - 1);
// 3.反转各个单词
reverseEachWord(sb);
return sb.toString();
}
private StringBuilder removeSpace(String 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++;
}
return sb;
}
/**
* 反转字符串指定区间[start, end]的字符
*/
public void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
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;
}
}
}
右旋转字符串
问题：字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。
可以通过两次子串局部翻转，再整体翻转一次解决，主要学习一下不同的翻转字符串方法。
代码示例：
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
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的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配，如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。
什么是前缀表？用KMP一定都写过next数组，那么这个next数组究竟是个啥呢？next数组就是一个前缀表（prefix table）。前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。比如要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf，文本串中第六个字符b 和 模式串的第六个字符f，不匹配了，如果暴力匹配，发现不匹配，此时就要从头匹配了，但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始匹配。
前缀表是如何记录的呢？他是记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串，后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串，所以字符串a的最长相等前后缀为0。 字符串aa的最长相等前后缀为1。 字符串aaa的最长相等前后缀为2。 等等…..
如何计算前缀表？长度为前1个字符的子串a，最长相同前后缀的长度为0；长度为前2个字符的子串aa，最长相同前后缀的长度为1；长度为前3个字符的子串aab，最长相同前后缀的长度为0；长度为前4个字符的子串aaba，最长相同前后缀的长度为1；长度为前5个字符的子串aabaa，最长相同前后缀的长度为2；长度为前6个字符的子串aabaaf，最长相同前后缀的长度为0，以此结果形成前缀表。
前缀表使用。若找到不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少，前一个字符的前缀表的数值是2， 所以把下标移动到下标2的位置继续比配。
前缀表和next数组。这方面并不涉及到KMP的原理，而是具体实现，next数组既可以就是前缀表，也可以是前缀表统一减一。
实现 strStr()
问题：给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
为KMP算法量身打造的一道题，找到匹配项开始的下标，如不理解可以去看本节一开始对KMP算法的详细介绍说明。
代码示例：
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
class Solution {
//前缀表（不减一）Java实现
public int strStr(String haystack, String needle) {
if (needle.length() == 0) return 0;
int[] next = new int[needle.length()];
getNext(next, needle);
int j = 0;
for (int i = 0; i < haystack.length(); i++) {
while (j > 0 && needle.charAt(j) != haystack.charAt(i))
j = next[j - 1];
if (needle.charAt(j) == haystack.charAt(i))
j++;
if (j == needle.length())
return i - needle.length() + 1;
}
return -1;
}
private void getNext(int[] next, String s) {
int j = 0;
next[0] = 0;
for (int i = 1; i < s.length(); i++) {
while (j > 0 && s.charAt(j) != s.charAt(i))
j = next[j - 1];
if (s.charAt(j) == s.charAt(i))
j++;
next[i] = j;
}
}
}
重复的子字符串
问题：给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
这道题我们可以先使用移动匹配的方法，即对于一个由重复子串多次构成的字符串，对于s+s即将两个同样的字符串拼接起来的大字符串，那么其在中间部分就一定能再拼接成一个s，我们可以去除s+s的首尾字符，在其中寻找是否还有一个s，这种方法实现的最后其实还是用到了KMP算法，我们可以自己来实现以下KMP算法的部分。
我们还可以使用KMP算法中的next数组来直接帮助我们找到重复子串，简单记结论：最长相等前后缀不包含的子串就是最小重复子串，数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被数组长度整除，就说明整个数组就是这个周期的循环。
我自己是采用手写KMP算法的方式来完成该题的，不使用库函数锻炼一下自己。
代码示例：
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
class Solution {
public void getNext(int[] next, String s) {
char[] ch = s.toCharArray();
int j = 0;
next[0] = 0;
for(int i = 1; i < s.length(); i++){
while(j > 0 && ch[i] != ch[j])
j = next[j-1];
if(ch[i] == ch[j])
j++;
next[i] = j;
}
}
public boolean strStr(String string, String s) {
int[] next = new int[s.length()];
getNext(next, s);
int j = 0;
for(int i = 0; i < string.length(); i++){
while(j > 0 && string.charAt(i) != s.charAt(j))
j = next[j-1];
if(string.charAt(i) == s.charAt(j))
j++;
if(j == s.length())
return true;
}
return false;
}
public boolean repeatedSubstringPattern(String s) {
String string = s + s;
string = string.substring(1, string.length() - 1);
return strStr(string, s);
}
}