字符串

反转字符串 - LeetCode 344

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 - LeetCode 541

• 每隔2k个字符，反转2k个字符
• 如果剩余字符小于2k，但大于或等于k个，则反转前k个字符

KMP

• 前缀表(next数组)是用来记录字符串前缀和后缀的最长公共部分
• 前缀表的目的是：当字符串匹配失败时，知道从哪里开始重新匹配
• 前缀定义：字符串的子串中，从开始到某个位置为止（不包含该位置），称为前缀
• 后缀定义：字符串的子串中，从某个位置开始到结束，称为后缀
• 最长相等前后缀：字符串的前缀和后缀的最长公共部分，也就是前缀表
• 如果不匹配了，跳到下标为前缀表的值的位置继续匹配
• 举例

字符串：aabaaf
前缀表：0 1 0 1 2 0
跳到下标为2的位置继续匹配b

反转字符串的单词 - LeetCode 151

• 倒着遍历字符串
• 边界要注意："the sky is blue"

public String reverseWords(String s) {
    StringBuilder res = new StringBuilder();
    int right = s.length() - 1;
    
    while (right >= 0) {
        if (s.charAt(right) == ' ') {
            right--; // 跳过空格
        } else {
            int left = right;
            while (left >= 0 && s.charAt(left) != ' ') {
                left--; // 定位单词起始
            }
            res.append(s, left + 1, right + 1).append(" ");
            right = left; // 跳过已处理单词
        }
    }
    return res.toString().trim(); // 移除末尾空格
}