【算法方法总结·四】字符串操作的一些技巧和注意事项

• 【算法方法总结·一】二分法的一些技巧和注意事项
• 【算法方法总结·二】双指针的一些技巧和注意事项
• 【算法方法总结·三】滑动窗口的一些技巧和注意事项
• 【算法方法总结·四】字符串操作的一些技巧和注意事项 🎯
• 【算法方法总结·五】链表操作的一些技巧和注意事项
• 【算法方法总结·六】栈队列堆的一些技巧和注意事项

---

【字符串操作】

此章节涉及到以下 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;
    }
}

---

相关力扣题

• 相关解法见【算法题解答·四】字符串操作

151.反转字符串中的单词

28.找出字符串中第一个匹配项的下标

459.重复的子字符串