【算法方法总结·四】字符串操作的一些技巧和注意事项
【算法方法总结·四】字符串操作的一些技巧和注意事项
- 【算法方法总结·一】二分法的一些技巧和注意事项
- 【算法方法总结·二】双指针的一些技巧和注意事项
- 【算法方法总结·三】滑动窗口的一些技巧和注意事项
- 【算法方法总结·四】字符串操作的一些技巧和注意事项
【字符串操作】
此章节涉及到以下 3 个问题
- （1）API
- （2）自定义方法
- （3）字符串匹配
API
关于 String 的一些常用用法
String str = "abca";
// 1、字符串大小 length()
int len = str.length(); // 4
// 2、将字符串对象中的字符转换为一个字符数组 toCharArray()
char[] ss = str.toCharArray();
for (char c : str.toCharArray()){
System.out.print(c + " "); // 输出：a b c d
}
// 3、字符数组 -> 字符串 valueOf()
String s = String.valueOf(ss); // abcd
// 4、区分大小写 equals()
boolean isEqual1 = str.equals("abcA"); // false
// 5、不区分大小写 equalsIgnoreCase()
boolean isEqual2 = str.equalsIgnoreCase("AbcA"); // true
// 6、返回字符在字符串第一次出现的索引
int idx1 = str.indexOf('a'); // 0
// 7、返回字符在字符串最后一次出现的索引
int idx2 = str.lastIndexOf('a'); // 3
// 8、从索引n开始截取后面所有的内容 substring(n)
String substr1 = str.substring(2); // ca
// 9、从索引i开始截取，到第n个字符[i,n) substring(i,n)
String substr2 = str.substring(1,3); // bc
// 10、转为大写
String upper = str.toUpperCase(); // ABCA
// 11、转为小写
String lower = str.toLowerCase(); // abca
// 12、拼接字符串
String newStr = str.concat("123"); // abca123
// 13、用y替代x replace(x,y)
String replaced = str.replace('a','z'); //zbcz
// 14、分割字符串(某些字符需要转移) split()
String splitStr = "a,b,c";
String[] parts = splitStr.split(","); // {"a","b","c"}
// 15、前者大，返回正，后者大，返回负，相等为0
str.compareTo()
// 16、格式化字符串(与c语言类似)
str.format()
// 17、移除字符串两端空白字符
str.trim()
自定义方法
很多地方会 要求不能 使用 Java 的 API 函数，所以有些方法得会 自己写
例如 151.反转字符串中的单词
1.移除多余空格（首尾空格）
// 1、移除多余空格
private StringBuilder reverseSpace(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);
// 当前字符c与sb串尾字符不同时为' '时，加入sb
if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
start++;
}
return sb;
}
2.将整个字符串反转
// 2、将整个字符串反转
public void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char t = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, t);
start++;
end--;
}
}
3.将每个单词反转
private void reverseEachWord(StringBuilder sb) {
int start = 0;
int end = 1;
int n = sb.length();
while (start < n) {
// 找到单词末尾的空格的索引end
while (end < n && sb.charAt(end) != ' ') {
end++;
}
// end-1为单词末尾的索引
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
字符串匹配
KMP 算法
-
当出现 字符串不匹配 时，可以知道一部分 之前已经匹配 的文本内容，可以利用这些信息避免从头再去 做匹配了
-
next 数组 就是一个前缀表，记录下标
i之前（包括i）的字符串中，有多大长度的相同前缀后缀 -
前缀表 是用来 回退 的，它记录了 模式串 与 主串（文本串） 不匹配的时候，模式串应该从哪里开始重新匹配
最长公共前后缀（这里用了 宫水三叶 的图便于理解）
-
前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
-
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
next 数组的构建
- 前缀 是指 不包含最后一个字符 的所有以第一个字符开头的连续子串。
- 后缀 是指 不包含第一个字符 的所有以最后一个字符结尾的连续子串。
next数组有 很多种不同的写法，但只影响 其不匹配时 寻找 重新匹配位置 的方法j指向 前缀末尾 位置，i指向 后缀末尾 位置- 在这里我采取了
next和 前缀表PM相同的方法，在这种情况下，重新匹配位置 看前一个位置的next数组，如下图所示，j=1, i=2, s[j]!=s[i]时，需要重新匹配，j要回退到前一个位置的next数组（即next[j-1]）
// 得到 next数组，其实就是 PM 数组
public void getNext(int[] next, String s) {
char[] ss = s.toCharArray();
// j 指向前缀末尾位置，i 指向后缀末尾位置
int j = 0;
next[0] = 0; // 第一位为 0
for(int i = 1; i < s.length(); i++) {
// 不匹配时，循环回退 j
while(j > 0 && ss[i] != ss[j]){
j = next[j - 1];
}
// 匹配时，j++，继续匹配
if(ss[i] == ss[j]){
j++;
}
// j 同时也指前后缀相等的个数
next[i] = j;
}
}
相关力扣题
- 相关解法见【算法题解答·四】字符串操作