【算法】字符串

g0dam

2024-10-16

Algorithm

字符串

344.反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：
输入：s = [“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]

示例 2：
输入：s = [“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]

使用双指针解决这个问题,同时可以用异或来交换数值

class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while(l < r){
            s[l] ^= s[r];
            s[r] ^= s[l];
            s[l] ^= s[r];
            l++;
            r--;
        }
    }
}

541. 反转字符串II

给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。

如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例:
输入: s = “abcdefg”, k = 2
输出: “bacdfeg”

class Solution {
    public String reverseStr(String s, int k) {
        StringBuffer res = new StringBuffer();
        int length = s.length();
        int start = 0;
        while(start < length){
            StringBuffer temp = new StringBuffer();
            // 与length进行判断,,如果大了就将其置为length
            int firstK = (start + k > length) ? length : start + k;
            int secondK = (start + (2*k) > length) ? length : start + (2*k);
            // 无论start的位置,至少会反转一次
            temp.append(s.substring(start, firstK));
            res.append(temp.reverse());
            // 如果firstK到secondK之间有元素,这些元素直接放入res里
            if(firstK < secondK){
                res.append(s.substring(firstK, secondK));
            }
            start += (2*k);
        }
        return res.toString();
    }
}


// 每隔2k个反转前k个
class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for(int i = 0; i < ch.length; i+=2*k){
            int start = i;
            int end = Math.min(ch.length-1,start+k-1);
            while(start < end){
                ch[start] ^= ch[end];
                ch[end] ^= ch[start];
                ch[start] ^= ch[end];
                start++;
                end--;
            }
        }
        return new String(ch);
    }
}

替换数字

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。
例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。
对于输入字符串 “a5b”，函数应该将其转换为 “anumberb”
输入：一个字符串 s,s 仅包含小写字母和数字字符。
输出：打印一个新的字符串，其中每个数字字符都被替换为了number
样例输入：a1b2c3
样例输出：anumberbnumbercnumber
数据范围：1 <= s.length < 10000

如果想把这道题目做到极致，就不要只用额外的辅助空间了！（不过使用Java刷题的录友，一定要使用辅助空间，因为Java里的string不能修改）
首先扩充数组到每个数字字符替换成 “number” 之后的大小。
例如字符串 “a5b” 的长度为3，那么将数字字符变成字符串 “number” 之后的字符串为 “anumberb” 长度为 8。

然后从后向前替换数字字符，也就是双指针法，过程如下：i指向新长度的末尾，j指向旧长度的末尾。

有同学问了，为什么要从后向前填充，从前向后填充不行么？
从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素整体向后移动。
其实很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

这么做有两个好处：

不用申请新数组。
从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

import java.util.Scanner;

public class Main {
    
    public static String replaceNumber(String s) {
        int count = 0; // 统计数字的个数
        int sOldSize = s.length();
        for (int i = 0; i < s.length(); i++) {
            if(Character.isDigit(s.charAt(i))){
                count++;
            }
        }
        // 扩充字符串s的大小，也就是每个空格替换成"number"之后的大小
        char[] newS = new char[s.length() + count * 5];
        int sNewSize = newS.length;
        // 将旧字符串的内容填入新数组
        System.arraycopy(s.toCharArray(), 0, newS, 0, sOldSize);
        // 从后先前将空格替换为"number"
        for (int i = sNewSize - 1, j = sOldSize - 1; j < i; j--, i--) {
            if (!Character.isDigit(newS[j])) {
                newS[i] = newS[j];
            } else {
                newS[i] = 'r';
                newS[i - 1] = 'e';
                newS[i - 2] = 'b';
                newS[i - 3] = 'm';
                newS[i - 4] = 'u';
                newS[i - 5] = 'n';
                i -= 5;
            }
        }
        return new String(newS);
    };
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        System.out.println(replaceNumber(s));
        scanner.close();
    }
}

// 为了还原题目本意，先把原数组复制到扩展长度后的新数组，然后不再使用原数组、原地对新数组进行操作。
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int len = s.length();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= 0 && s.charAt(i) <= '9') {
                len += 5;
            }
        }
        
        char[] ret = new char[len];
        for (int i = 0; i < s.length(); i++) {
            ret[i] = s.charAt(i);
        }
        for (int i = s.length() - 1, j = len - 1; i >= 0; i--) {
            if ('0' <= ret[i] && ret[i] <= '9') {
                ret[j--] = 'r';
                ret[j--] = 'e';
                ret[j--] = 'b';
                ret[j--] = 'm';
                ret[j--] = 'u';
                ret[j--] = 'n';
            } else {
                ret[j--] = ret[i];
            }
        }
        System.out.println(ret);
    }
}

151.翻转字符串里的单词

给你一个字符串 s ，请你反转字符串中单词的顺序。
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：
输入：s = “the sky is blue”
输出：”blue is sky the”

示例 2：
输入：s = “ hello world “
输出：”world hello”
解释：反转后的字符串中不能存在前导空格和尾随空格。

想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。

所以解题思路如下：

移除多余空格
将整个字符串反转
将每个单词反转
举个例子，源字符串为：”the sky is blue “
移除多余空格 : “the sky is blue”
字符串反转：”eulb si yks eht”
单词反转：”blue is sky the”

class Solution {
    public String reverseWords(String s) {
        // 去除首尾及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 反转各个单词
        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;
    }

    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;
        }
    }
}

//解法二：创建新字符数组填充。时间复杂度O(n)
class Solution {
    public String reverseWords(String s) {
        char[] initiaArr = s.toCharArray();
        char[] newArr = new char[initiaArr.length + 1]; //下面循环添加"单词 "，最终末尾的空格不会返回
        int newArrPos = 0;
        int i = initiaArr.length - 1;
        while(i >= 0){
            while(i >= 0 && initiaArr[i] == ' '){i--;} // 跳过空格
            // 此时i位置是边界或!=空格，先记录当前索引，之后的while用来确定字母的首字母位置
            int right = i;
            while(i>=0 && initiaArr[i] != ' '){i--;}
            // 指定区间单词取出（由于i为首字母的前一位，所以这里+1,取出的每组末尾都带有一个空格
            for(int j = i+1; j <= right; j++){
                newArr[newArrPos++] = initiaArr[j];
                if(j == right){
                    newArr[newArrPos++] = ' '; //空格
                }
            }
        }
        // 若是原是字符没有单词直接返回字符串，若是有单词，返回0-末尾空格索引前范围的字符数组(转成String返回)
        if(newArrPos == 0){
            return "";
        }else{
            return new String(newArr, 0, newArrPos-1);
        }
    }
}

//解法三：双反转+移位，String 的 toCharArray() 方法底层会 new 一个和原字符串相同大小的 char 数组，空间复杂度：O(n)
class Solution {
    /**
     * 思路：
     *	①反转字符串  "the sky is blue " => " eulb si yks eht"
     *	②遍历 " eulb si yks eht"，每次先对某个单词进行反转再移位
     *	   这里以第一个单词进行为演示：" eulb si yks eht" ==反转=> " blue si yks eht" ==移位=> "blue si yks eht"
     */
    public String reverseWords(String s) {
        //步骤1：字符串整体反转（此时其中的单词也都反转了）
        char[] initialArr = s.toCharArray();
        reverse(initialArr, 0, s.length() - 1);
        int k = 0;
        for (int i = 0; i < initialArr.length; i++) {
            if (initialArr[i] == ' ') {
                continue;
            }
            int tempCur = i;
            while (i < initialArr.length && initialArr[i] != ' ') {
                i++;
            }
            for (int j = tempCur; j < i; j++) {
                if (j == tempCur) { //步骤二：二次反转
                    reverse(initialArr, tempCur, i - 1);//对指定范围字符串进行反转，不反转从后往前遍历一个个填充有问题
                }
                //步骤三：移动操作
                initialArr[k++] = initialArr[j];
                if (j == i - 1) { //遍历结束
                    //避免越界情况，例如=> "asdasd df f"，不加判断最后就会数组越界
                    if (k < initialArr.length) {
                        initialArr[k++] = ' ';
                    }
                }
            }
        }
        if (k == 0) {
            return "";
        } else {
            //参数三：以防出现如"asdasd df f"=>"f df asdasd"正好凑满不需要省略空格情况
            return new String(initialArr, 0, (k == initialArr.length) && (initialArr[k - 1] != ' ') ? k : k - 1);
        }
    }

    public void reverse(char[] chars, int begin, int end) {
        for (int i = begin, j = end; i < j; i++, j--) {
            chars[i] ^= chars[j];
            chars[j] ^= chars[i];
            chars[i] ^= chars[j];
        }
    }
}

/*
 * 解法四：时间复杂度 O(n)
 * 参考卡哥 c++ 代码的三步骤：先移除多余空格，再将整个字符串反转，最后把单词逐个反转
 * 有别于解法一 ：没有用 StringBuilder  实现，而是对 String 的 char[] 数组操作来实现以上三个步骤
 */
class Solution {
    //用 char[] 来实现 String 的 removeExtraSpaces，reverse 操作
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        //1.去除首尾以及中间多余空格
        chars = removeExtraSpaces(chars);
        //2.整个字符串反转
        reverse(chars, 0, chars.length - 1);
        //3.单词反转
        reverseEachWord(chars);
        return new String(chars);
    }

    //1.用 快慢指针 去除首尾以及中间多余空格，可参考数组元素移除的题解
    public char[] removeExtraSpaces(char[] chars) {
        int slow = 0;
        for (int fast = 0; fast < chars.length; fast++) {
            //先用 fast 移除所有空格
            if (chars[fast] != ' ') {
                //在用 slow 加空格。 除第一个单词外，单词末尾要加空格
                if (slow != 0)
                    chars[slow++] = ' ';
                //fast 遇到空格或遍历到字符串末尾，就证明遍历完一个单词了
                while (fast < chars.length && chars[fast] != ' ')
                    chars[slow++] = chars[fast++];
            }
        }
        //相当于 c++ 里的 resize()
        char[] newChars = new char[slow];
        System.arraycopy(chars, 0, newChars, 0, slow); 
        return newChars;
    }

    //双指针实现指定范围内字符串反转，可参考字符串反转题解
    public void reverse(char[] chars, int left, int right) {
        if (right >= chars.length) {
            System.out.println("set a wrong right");
            return;
        }
        while (left < right) {
            chars[left] ^= chars[right];
            chars[right] ^= chars[left];
            chars[left] ^= chars[right];
            left++;
            right--;
        }
    }

    //3.单词反转
    public void reverseEachWord(char[] chars) {
        int start = 0;
        //end <= s.length() 这里的 = ，是为了让 end 永远指向单词末尾后一个位置，这样 reverse 的实参更好设置
        for (int end = 0; end <= chars.length; end++) {
            // end 每次到单词末尾后的空格或串尾,开始反转单词
            if (end == chars.length || chars[end] == ' ') {
                reverse(chars, start, end - 1);
                start = end + 1;
            }
        }
    }
}

右旋字符串

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。
输入：输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。
输出：输出共一行，为进行了右旋转操作后的字符串。

输入示例
2
abcdefg
输出示例
fgabcde

为了让本题更有意义，提升一下本题难度：不能申请额外空间，只能在本串上操作。（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--;
        }
    }
}

// 版本二
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 - n - 1);  //反转前一段字符串，此时的字符串首尾是0,len - n - 1
        reverseString(chars, len - n, len - 1);  //反转后一段字符串，此时的字符串首尾是len - n,len - 1
        reverseString(chars, 0, 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--;
        }
    }
}

28. 实现 strStr()

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：
输入：haystack = “sadbutsad”, needle = “sad”
输出：0
解释：”sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：
输入：haystack = “leetcode”, needle = “leeto”
输出：-1
解释：”leeto” 没有在 “leetcode” 中出现，所以返回 -1 。

class Solution {
    /**
     * 基于窗口滑动的算法
     * <p>
     * 时间复杂度：O(m*n)
     * 空间复杂度：O(1)
     * 注：n为haystack的长度，m为needle的长度
     */
    public int strStr(String haystack, String needle) {
        int m = needle.length();
        // 当needle是空字符串时我们应当返回0
        if(m == 0){
            return 0;
        }
        int n = haystack.length();
        if(n < m){
            return -1;
        }
        int i = 0;
        int j = 0;
        while(i < n-m+1){
            //找到首字母相等
            while(i < n && haystack.charAt(i) != needle.charAt(j)){
                i++;
            }
            if(i == n){
                return -1;
            }
            // 遍历后续字符，判断是否相等
            i++;
            j++;
            while(i < n && j < m && haystack.charAt(i) == needle.charAt(j)){
                i++;
                j++;
            }
            if(j == m){
                return i-j;
            }else{
                i -= j - 1;
                j = 0;
            }
        }
        return -1;
    }
}

// KMP解法，next数组首位-1的方法
class Solution {
    public void getNext(int[] next, String s){
        int j = -1;
        next[0] = j;
        for(int i = 1; i < s.length(); i++){
            while(j >= 0 && s.charAt(i) != s.charAt(j+1)){
                j = next[j];
            }
            if(s.charAt(i) == s.charAt(j+1)){
                j++;
            }
            next[i] = j;
        }
    }
    public int strStr(String haystack, String needle) {
        if(needle.length() == 0){
            return 0;
        }

        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = -1;
        for(int i = 0; i < haystack.length(); i++){
            while(j >= 0 && haystack.charAt(i) != needle.charAt(j+1)){
                j = next[j];
            }
            if(haystack.charAt(i) == needle.charAt(j+1)){
                j++;
            }
            if(j == needle.length() - 1){
                return (i-needle.length() + 1);
            }
        }
        return -1;
    }
}

KMP算法

这道题其实核心算法是KMP算法,写过KMP的同学，一定都写过next数组，那么这个next数组究竟是个啥呢？next数组就是一个前缀表（prefix table）。
前缀表有什么作用呢？前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
为了清楚地了解前缀表的来历，我们来举一个例子：
要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。前缀表是如何记录的呢？
首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。
那么什么是前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

刚刚匹配的过程在下标5的地方遇到不匹配，模式串是指向f，如图：

然后就找到了下标2，指向b，继续匹配：如图：

下标5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀和后缀字符串是子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了

如何计算前缀表

长度为前1个字符的子串a，最长相同前后缀的长度为0。（注意字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。）

长度为前2个字符的子串aa，最长相同前后缀的长度为1。

长度为前3个字符的子串aab，最长相同前后缀的长度为0。
以此类推：长度为前4个字符的子串aaba，最长相同前后缀的长度为1。长度为前5个字符的子串aabaa，最长相同前后缀的长度为2。长度为前6个字符的子串aabaaf，最长相同前后缀的长度为0。
那么把求得的最长相同前后缀的长度就是对应前缀表的元素，如图：

可以看出模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

前缀表与next数组
很多KMP算法的实现都是使用next数组来做回退操作，那么next数组与前缀表有什么关系呢？
next数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。
为什么这么做呢，其实这并不涉及到KMP的原理，而是具体实现，next数组既可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为-1）。

时间复杂度分析：其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。

459.重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:
输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成

示例 2:
输入: s = “aba”
输出: false

示例 3:
输入: s = “abcabcabcabc”
输出: true
解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)

暴力解法

暴力的解法，就是一个for循环获取子串的终止位置，然后判断子串是否能重复构成字符串，又嵌套一个for循环，所以是O(n^2)的时间复杂度。
有的同学可以想，怎么一个for循环就可以获取子串吗？至少得一个for获取子串起始位置，一个for获取子串结束位置吧。
其实我们只需要判断，以第一个字母为开始的子串就可以，所以一个for循环获取子串的终止位置就行了。而且遍历的时候都不用遍历结束，只需要遍历到中间位置，因为子串结束位置大于中间位置的话，一定不能重复组成字符串。

结合KMP解法

假设我们有一个字符串 s = "abcabc"，我们想要判断这个字符串是否由一个更短的子串通过重复组成的。

第一步：理解字符串重复的基本概念
如果字符串 s 由重复的子串组成，比如 s = "abcabc" 可以看作是 "abc" 重复了两次。这就意味着，如果我们对 s 进行一定的操作，应该能够从中发现重复的模式。
第二步：构造新字符串
为了探索这种可能的重复模式，我们可以尝试将字符串 s 复制并拼接自身，形成一个新的字符串 t = s + s，即 t = "abcabcabcabc"。
第三步：去除首尾字符
接下来，我们去掉 t 的首尾字符，这样可以防止我们仅仅是在新字符串的开始或结束处找到原始的 s。去掉首尾字符后，t 变成 "bcabcabcab"。
第四步：搜索原始字符串
现在，如果在处理后的字符串 t 中仍然能找到原始的字符串 s，这表明 s 确实是由重复的子串组成的。在我们的例子中，"abcabc" 确实出现在 "bcabcabcab" 中，从索引 1 到 6。
第五步：理解KMP算法的应用
在实际的算法实现中，为了提高搜索的效率，可以使用 KMP 算法。KMP 算法通过预计算一个所谓的”部分匹配表”（也称为 next 数组），来优化搜索过程。这个数组帮助算法在不匹配时，跳过无需比较的部分。
第六步：代码实现和复杂度分析
在代码实现中，这个原理可以简单地通过检查 t.find(s) != std::string::npos 来实现，即检查 s 是否作为子串存在于 t 中。这种方法的时间复杂度通常为 O(n)，空间复杂度为 O(1)。

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;
        }

        if(next[len] > 0 && len % (len - next[len]) == 0){
            return true;
        }
        return false;
    }
}

字符串：总结篇

双指针法

在344.反转字符串 (opens new window)，我们使用双指针法实现了反转字符串的操作，双指针法在数组，链表和字符串中很常用。
接着在字符串：替换空格 (opens new window)，同样还是使用双指针法在时间复杂度O(n)的情况下完成替换空格。
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
那么针对数组删除操作的问题，其实在27. 移除元素 (opens new window)中就已经提到了使用双指针法进行移除操作。
同样的道理在151.翻转字符串里的单词 (opens new window)中我们使用O(n)的时间复杂度，完成了删除冗余空格。
一些同学会使用for循环里调用库函数erase来移除元素，这其实是O(n^2)的操作，因为erase就是O(n)的操作，所以这也是典型的不知道库函数的时间复杂度，上来就用的案例了。

反转系列

在反转上还可以在加一些玩法，其实考察的是对代码的掌控能力。
541.反转字符串II (opens new window)中，一些同学可能为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。
其实当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。
只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。
因为要找的也就是每2 * k 区间的起点，这样写程序会高效很多。
在151.翻转字符串里的单词 (opens new window)中要求翻转字符串里的单词，这道题目可以说是综合考察了字符串的多种操作。是考察字符串的好题。
这道题目通过先整体反转再局部反转，实现了反转字符串里的单词。
后来发现反转字符串还有一个牛逼的用处，就是达到左旋的效果。
在字符串：反转个字符串还有这个用处？ (opens new window)中，我们通过先局部反转再整体反转达到了左旋的效果。

KMP

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
KMP的精髓所在就是前缀表，在KMP精讲 (opens new window)中提到了，什么是KMP，什么是前缀表，以及为什么要用前缀表。
前缀表：起始位置到下标i之前（包括i）的子串中，有多大长度的相同前缀后缀。
那么使用KMP可以解决两类经典问题：
匹配问题：28. 实现 strStr()(opens new window)
重复子串问题：459.重复的子字符串(opens new window)
再一次强调了什么是前缀，什么是后缀，什么又是最长相等前后缀。
前缀：指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀：指不包含第一个字符的所有以最后一个字符结尾的连续子串。
然后针对前缀表到底要不要减一，这其实是不同KMP实现的方式，我们在KMP精讲 (opens new window)中针对之前两个问题，分别给出了两个不同版本的的KMP实现。
其中主要理解j=next[x]这一步最为关键！

常见算法思路与实现

字符串反转 (344. 反转字符串)

使用双指针法来原地反转字符串，这种方法时间复杂度为 O(n)，空间复杂度为 O(1)。

代码示例:

public void reverseString(char[] s) {
    int left = 0, right = s.length - 1;
    while (left < right) {
        char temp = s[left];
        s[left++] = s[right];
        s[right--] = temp;
    }
}

局部字符串反转 (541. 反转字符串 II)

对特定的子串进行反转，可用于加密、文本处理等场景。

代码示例:

public String reverseStr(String s, int k) {
    char[] a = s.toCharArray();
    for (int start = 0; start < a.length; start += 2 * k) {
        int i = start, j = Math.min(start + k - 1, a.length - 1);
        while (i < j) {
            char tmp = a[i];
            a[i++] = a[j];
            a[j--] = tmp;
        }
    }
    return new String(a);
}

字符串中的单词翻转 (151. 翻转字符串里的单词)

先移除多余空格，再整体反转字符串，最后反转每个单词。

代码示例:

public String reverseWords(String s) {
    s = s.trim(); // 去掉首尾空格
    String[] words = s.split("\\s+"); // 正则匹配连续空格
    Collections.reverse(Arrays.asList(words));
    return String.join(" ", words);
}

KMP算法 (28. 实现 strStr())

KMP 是用于字符串搜索的高效算法，通过计算“部分匹配”表来减少比较次数。

代码示例:

public int strStr(String haystack, String needle) {
    if (needle.isEmpty()) return 0;
    int[] lps = computeLPSArray(needle);
    int i = 0, j = 0;
    while (i < haystack.length()) {
        if (haystack.charAt(i) == needle.charAt(j)) {
            i++; j++;
        }
        if (j == needle.length()) {
            return i - j;
        } else if (i < haystack.length() && haystack.charAt(i) != needle.charAt(j)) {
            if (j != 0) j = lps[j - 1];
            else i++;
        }
    }
    return -1;
}

替换数字为字符串 (自定义题目)

针对字符串中的数字字符进行特定字符串的替换。

代码示例:

public String replaceDigits(String s) {
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) sb.append("number");
        else sb.append(c);
    }
    return sb.toString();
}