leetcode--字符串

344.反转字符串

541.反转字符串II

卡码网：替换数字

151.反转字符串中的单词

卡码网：右旋字符串

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

459.重复的子字符串

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"]
提示：

1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符

原理

该算法使用两个指针（left 和 right）从字符串的两端开始逐步交换字符，直到两个指针相遇或交错。由于每次交换两个字符，且每个字符最多交换一次，因此时间复杂度是 O(n)，其中 n 是字符串的长度。

空间复杂度：由于只使用了常数级别的空间来存储临时字符（c），没有分配额外的数组或数据结构，因此空间复杂度是 O(1)。
时间复杂度：需要遍历字符串的一半来交换字符，因此时间复杂度是 O(n)，其中 n 是输入字符串的长度。

代码

class Solution {public void reverseString(char[] s) {// 初始化两个指针，left 指向数组的开头，right 指向数组的末尾int left = 0, right = s.length - 1;// 使用 while 循环，当 left 指针小于 right 指针时继续反转while (left < right) {// 使用一个临时变量 c 保存 s[left] 的值char c = s[left];// 将 s[left] 和 s[right] 的值交换s[left] = s[right];s[right] = c;// 移动左指针和右指针，向中间靠拢left++;right--;}}
}

541.反转字符串II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

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

示例 1：
输入：s = "abcdefg", k = 2
输出："bacdfeg"
示例 2：
输入：s = "abcd", k = 2
输出："bacd"
提示：

1 <= s.length <= 104
s 仅由小写英文组成
1 <= k <= 104

原理

字符分组和反转：

根据题目要求，首先将字符串分成每 2k 个字符为一组。对于每一组，反转前 k 个字符，后 k 个字符不变。
如果剩余字符数小于 k，那么将这些字符全部反转。如果剩余字符数大于等于 k，则仅反转前 k 个字符。

过程示例：假设输入 s = "abcdefg" 和 k = 2，输出为 "bacdfeg"。按照步骤：

第一组 ["a", "b", "c", "d"]：反转前 k=2 个字符，得到 ["b", "a", "c", "d"]。
第二组 ["e", "f", "g"]：只反转前 k=2 个字符，得到 ["f", "e", "g"]。
最终输出结果为 "bacdfeg"。

空间复杂度：

由于使用了一个字符数组 str 来保存修改后的结果，空间复杂度是 O(n)，其中 n 是字符串的长度。实际上，只有一个字符数组被用来做原地修改，空间复杂度也没有额外增加。

时间复杂度：

每次反转操作的时间复杂度是 O(k)，但每组反转的操作总数为 O(n / (2k))。因此，主循环的时间复杂度是 O(n)。
总的时间复杂度为 O(n)。

代码

class Solution {public String reverseStr(String s, int k) {// 获取字符串长度int len = s.length();// 计算余数和剩余字符长度int len1 = len % (2 * k);  // 计算剩余字符是否少于 2kint len2 = len - len1;     // 计算可以完整处理的部分长度// 将字符串转换为字符数组进行原地修改char[] str = s.toCharArray();// 每 2k 个字符进行处理，反转前 k 个字符for (int i = 0; i < len2 / (2 * k); i++) {reverseString(str, 2 * i * k, 2 * i * k + k - 1);  // 反转前 k 个字符}// 处理剩余字符的情况if (0 < len1 && len1 < k) {reverseString(str, len2, len - 1);  // 如果剩余字符少于 k，反转所有剩余字符} else if (len1 >= k) {reverseString(str, len2, len2 + k - 1);  // 如果剩余字符大于等于 k，反转前 k 个字符}// 将字符数组转换回字符串并返回String ans = new String(str);return ans;}// 辅助函数：反转字符串的一部分public void reverseString(char[] str, int left, int right) {while (left < right) {char c = str[left];str[left] = str[right];str[right] = c;left++;right--;}}
}

原理

该算法的核心思想是将字符串每 2k 个字符分成两部分，前 k 个字符反转，后 k 个字符保持不变。遍历整个字符串时，按此规则逐步反转每个子串。

步骤：

分组反转：每 2k 个字符为一组，反转每一组的前 k 个字符。后 k 个字符保持不变。如果剩余字符少于 k，反转所有剩余字符；如果剩余字符大于等于 k，则只反转前 k 个字符，后面的字符保持原样。

分组处理：

对于每一组的前 k 个字符，调用 reverseString 方法进行反转。
使用 Math.min(k + i, len) 确保不会越界，当处理到字符串的末尾时，剩余字符数少于 2k 时，反转剩余字符或仅反转部分字符。

双指针反转：

reverseString 方法使用双指针的方式来反转字符数组中的指定部分。每次交换字符后，指针向中间靠拢，直到指针相遇。

时间复杂度：

reverseString 方法的时间复杂度为 O(k)，而每次循环处理 2k 个字符，总的处理次数为 O(n / (2k))。因此总的时间复杂度为 O(n)，其中 n 是字符串的长度。

空间复杂度：

使用了字符数组 str 来保存字符串，因此空间复杂度为 O(n)。

代码

class Solution {public String reverseStr(String s, int k) {// 获取字符串长度int len = s.length();// 将字符串转化为字符数组，因为字符串是不可变的，而字符数组可以原地修改char[] str = s.toCharArray();// 遍历字符串，每次处理 2k 个字符// i 每次增加 2k，表示处理下一个 2k 字符段for (int i = 0; i < len; i += (2 * k)) {// 调用反转方法，将每个 2k 字符段的前 k 个字符反转// Math.min(k + i, len) 处理剩余字符的情况，确保不越界reverseString(str, i, Math.min(k + i, len) - 1);}// 将修改后的字符数组转换回字符串并返回return new String(str);}// 辅助方法：反转字符数组中的一部分public void reverseString(char[] str, int left, int right) {// 使用两个指针来交换字符，直到指针相遇while (left < right) {char c = str[left];str[left] = str[right];str[right] = c;left++;right--;}}
}

卡码网：替换数字

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。

对于输入字符串 "a5b"，函数应该将其转换为 "anumberb"

输入：一个字符串 s,s 仅包含小写字母和数字字符。

输出：打印一个新的字符串，其中每个数字字符都被替换为了number

样例输入：a1b2c3

样例输出：anumberbnumbercnumber

数据范围：1 <= s.length < 10000。

原理

遍历字符串并统计数字字符：

首先遍历字符串，统计其中的数字字符。通过判断字符是否在 0 到 9 范围内，能够识别出数字字符。数字字符的数量将影响最终字符串的长度，因为每个数字字符会被替换为 "number"，即增加 5 个字符。

替换操作：

在遍历字符串时，遇到数字字符时，就将其替换为 "number"（长度为 6），而字母字符保持不变。这种方法避免了额外的空间开销，因为我们直接在一个新的字符数组中进行修改。

数组构建新字符串：

使用一个新的字符数组来存储替换后的字符，避免在原字符串上进行修改，因为字符串在 Java 中是不可变的。最终将字符数组转换为一个新的字符串并返回。

代码

public static String replaceNumber(String s) {// 变量 digitNum 用于统计字符串中数字的个数int digitNum = 0;// 遍历字符串，统计其中的数字字符for (int i = 0; i < s.length(); i++) {// 如果当前字符是数字字符（在字符 '0' 到 '9' 之间）if (s.charAt(i) <= '9' && s.charAt(i) >= '0') {digitNum++; // 统计数字的数量}}// 计算新的字符串的长度// 原始字符串长度 + 每个数字字符被替换为 "number" 的增加部分int lenNew = s.length() + 5 * digitNum;// 创建一个新的字符数组，用来存放结果char ans[] = new char[lenNew];// 定义 right 作为新字符串的位置指针int right = 0;// 遍历原始字符串for (int i = 0; i < s.length(); i++) {// 如果当前字符是数字if (s.charAt(i) <= '9' && s.charAt(i) >= '0') {// 将 "number" 逐个字符填入新的字符数组ans[right] = 'n';ans[right + 1] = 'u';ans[right + 2] = 'm';ans[right + 3] = 'b';ans[right + 4] = 'e';ans[right + 5] = 'r';right += 6; // 更新 right 指针} else {// 如果是字母字符，则直接将原字符填入新数组ans[right] = s.charAt(i);right++; // 更新 right 指针}}// 将字符数组转换为字符串并返回return new String(ans);
}

151.反转字符串中的单词

给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：
输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
提示：

1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词

原理

去除多余空格：

遍历输入字符串 s，将多余的空格移除。多余的空格包括：
开头和结尾的空格。
连续的空格。
用 words 数组来存储去除多余空格后的字符。

添加尾部空格：

如果去除多余空格后字符串的最后一个字符不是空格，向数组中加入一个空格，这样便于后续处理。

双指针方法反转单词顺序：

通过两个指针 start1 和 end1 来标记当前单词的位置，另一个指针 start2 和 end2 来标记反转后的目标位置。
每次遇到空格时，表示一个单词的结束，就将该单词从 words 数组中复制到 ans 数组的相应位置。
通过调整 end2 来确保每个单词之间用一个空格隔开。
最终得到的 ans 数组即为反转后的结果。

返回结果：

将 ans 数组转成字符串并返回。

时间复杂度分析：

遍历原字符串的时间复杂度为 O(n)，其中 n 为字符串 s 的长度。
对于每个单词的处理，使用 System.arraycopy 复制字符，最坏情况下也是 O(n)。
因此，总的时间复杂度为 O(n)。

空间复杂度分析：

使用了一个 words 数组来存储去除多余空格后的字符，大小为 O(n)，其中 n 为字符串长度。
使用了一个 ans 数组来存储最终结果，大小也是 O(n)。
因此，空间复杂度为 O(n)。

代码

class Solution {public String reverseWords(String s) {// 创建一个足够大的字符数组来存储处理后的字符串char[] words = new char[s.length() + 5];// 用来记录去除多余空格后的字符串的长度int lenwordS = 0;// 遍历原字符串，去除多余的空格for (int i = 0; i < s.length(); i++) {// 处理字符串的头部，如果第一个字符不是空格，直接加入if (i == 0) {if (s.charAt(0) != ' ') {words[lenwordS++] = s.charAt(0);}continue;}// 如果当前字符不是空格，或者当前字符是空格但前一个字符不是空格，则保留if (s.charAt(i) != ' ' || (s.charAt(i) == ' ' && s.charAt(i - 1) != ' ')) {words[lenwordS++] = s.charAt(i);}}// 如果去除多余空格后尾部最后一个字符不是空格，则加一个空格，方便后续处理if (words[lenwordS - 1] != ' ') {words[lenwordS] = ' ';lenwordS++;}// 使用双指针从前往后和从后往前处理字符串，反转单词顺序int start1 = 0, end1 = 0, end2 = lenwordS - 2, start2 = lenwordS - 2;char[] ans = new char[lenwordS - 1];// 遍历处理每个单词for (int i = 0; i < lenwordS; i++) {// 如果当前字符是空格，表示一个单词的结束if (words[i] == ' ') {// 设置当前单词的结束位置end1 = i - 1;// 计算反转后单词在结果字符串中的起始位置start2 = end2 - (end1 - start1);// 复制当前单词到结果数组int lensplit = end1 - start1 + 1;System.arraycopy(words, start1, ans, start2, lensplit);// 更新指针，准备处理下一个单词end2 -= (end1 - start1 + 1);if (end2 <= 0) {break;} else {// 在两个单词之间加入一个空格ans[end2] = ' ';end2--;}start1 = i + 1;end1 = i + 1;}}// 返回反转后的字符串return new String(ans);}
}

卡码网：右旋字符串

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。

输入：输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

输出：输出共一行，为进行了右旋转操作后的字符串。

样例输入：
2
abcdefg 
1
2

样例输出：
fgabcde
1

数据范围：1 <= k < 10000, 1 <= s.length < 10000

原理

字符串的右旋转操作：
对于一个字符串的右旋转操作，实际上就是将字符串分成两部分：

后面的 k 个字符。
前面的 n-k 个字符（其中 n 是字符串的长度）。
然后交换这两部分的位置，得到旋转后的字符串。

操作流程：

将前 n-k 个字符按顺序移到新字符串的后面位置。
将后 k 个字符按顺序移到新字符串的前面位置。
这种操作可以通过两个 for 循环来完成，分别处理前半部分和后半部分的字符位置。

优化：

如果 k 大于或等于字符串长度 n，直接返回原字符串，因为右旋转 n 次及其倍数的操作会得到相同的结果。
通过字符数组的操作避免了频繁的字符串拼接，效率较高。

时间复杂度分析：

时间复杂度：

转换字符串为字符数组：O(n)。
遍历字符串并将字符复制到新数组：O(n)，其中 n 为字符串的长度。
总时间复杂度为 O(n)。

空间复杂度：

需要一个与输入字符串长度相同的字符数组 ans，因此空间复杂度为 O(n)。

代码

public static void main(String[] args) {// 定义输入字符串和右旋转的位数String s = "abcdefg";int k = 2;// 调用反转字符串的函数，并输出结果String ans = reverseString(k, s);System.out.print(ans);
}// reverseString 方法用于实现字符串的右旋转
public static String reverseString(int k, String s) {// 将字符串转为字符数组，方便操作char[] words = s.toCharArray();// 创建一个新的字符数组来存储旋转后的结果char[] ans = new char[s.length()];// 如果旋转的位数大于或等于字符串的长度，则返回原字符串// 因为右旋转一整个字符串是没必要的if (k >= s.length()) {return s;}// 第一部分：将后面的 k 个字符移动到前面for (int i = 0; i < s.length() - k; i++) {ans[i + k] = words[i];}// 第二部分：将前面的 s.length() - k 个字符移动到后面for (int i = s.length() - k; i < s.length(); i++) {ans[i + k - s.length()] = words[i];}// 返回右旋转后的字符串return new String(ans);
}

原理

这个算法利用了三次反转的方法来实现字符串的右旋转，具体过程如下：

反转整个字符串：

首先反转整个字符串，得到一个“倒置”版本的字符串。例如，字符串 "abcdefg" 被反转为 "gfedcba"。

反转前 k 个字符：

反转前 k 个字符，将这些字符从倒置状态恢复到正确的顺序。例如，字符串 "gfedcba" 中的前 2 个字符 "gf" 被反转为 "fg"，结果变为 "fgedcba"。

反转后 n-k 个字符：

最后，反转从第 k 个字符到最后一个字符，将其恢复到正确的顺序。例如，字符串 "fgedcba" 中的部分 "edcba" 被反转为 "abcde"，结果最终得到 "fgabcde"。

通过这三次反转操作，原本的字符串 s 被成功地右旋转了 k 位。

时间复杂度分析：

每一次反转操作的时间复杂度为 O(n)，其中 n 是字符串的长度。因为每一次反转都需要遍历一部分字符数组。
总的时间复杂度为 O(n)，因为我们进行了三次反转，每次反转操作的时间复杂度都是线性的。

空间复杂度分析：

由于输入字符串是以字符数组的形式传递给函数的，我们需要一个额外的字符数组来存储输入字符串的副本。这个数组的大小是 O(n)，其中 n 是字符串的长度。
因此，空间复杂度是 O(n)。

代码

public static void main(String[] args) {// 输入字符串和旋转的位数String s = "abcdefg";int k = 2;// 将字符串转换为字符数组，以便进行操作char[] word = s.toCharArray();// 第一次反转整个字符数组reverseString(0, s.length() - 1, word);// 第二次反转前 k 个字符reverseString(0, k - 1, word);// 第三次反转从第 k 个字符到最后一个字符reverseString(k, s.length() - 1, word);// 输出最终的字符数组，自动转为字符串System.out.print(word);
}// 反转字符数组中的一部分
public static void reverseString(int start, int end, char[] s) {// 当起始位置小于结束位置时，交换字符，直到两个指针相遇while (start < end) {// 交换字符char temp = s[start];s[start] = s[end];s[end] = temp;// 移动指针start++;end--;}
}

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

给你两个字符串 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 。
提示：

1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成

原理

该算法的核心是暴力匹配法。它通过以下步骤来实现：

遍历：从 haystack 字符串的每个位置开始，尝试匹配 needle 字符串。
匹配：当找到一个字符相同的位置时，进一步检查 needle 中的所有字符是否与 haystack 中的字符匹配。
返回结果：如果找到匹配项，返回其起始位置；如果遍历结束后没有找到，返回 -1。

时间复杂度分析：

外层循环遍历了 haystack 的每个字符，最多执行 haystack.length() - needle.length() + 1 次。
内层循环最多遍历 needle.length() 次。
因此，最坏情况下的时间复杂度是 O((n - m + 1) * m)，其中 n 是 haystack 的长度，m 是 needle 的长度。最坏情况下这个复杂度为 O(n * m)。

空间复杂度分析：

该算法仅使用了常量级的额外空间，因此空间复杂度为 O(1)。

代码

class Solution {// strStr 方法用于查找 haystack 中首次出现 needle 的位置public int strStr(String haystack, String needle) {// 如果 needle 为空字符串，根据题目要求应返回 0if (needle.isEmpty()) {return 0;}// 遍历 haystack 字符串，检查每个位置是否能匹配 needlefor (int i = 0; i < haystack.length() - needle.length() + 1; i++) {// 如果当前 haystack 字符与 needle 的第一个字符相同，则可能是匹配的开始if (haystack.charAt(i) == needle.charAt(0)) {boolean flag = true; // 用于标记是否匹配// 从 haystack[i] 开始，逐个字符与 needle 比较for (int j = 1; j < needle.length(); j++) {// 如果对应位置字符不同，则标记为不匹配并退出内层循环if (needle.charAt(j) != haystack.charAt(i + j)) {flag = false;break;}}// 如果匹配成功，返回起始位置 iif (flag == true) {return i;}}}// 如果没有找到匹配，返回 -1return -1;}
}

原理

KMP 算法是一种优化的字符串匹配算法，其关键在于通过构建一个 next 数组，避免了重复的字符比较。具体原理如下：

部分匹配信息：
next[i] 存储的是 needle[0...i] 字符串的最长相同前后缀的长度。例如，对于 needle = "ABAB"，next 数组为 [0, 0, 1, 2]。

匹配过程：
在匹配过程中，若发现字符不匹配，传统的暴力算法会直接从头开始重新匹配。而 KMP 算法利用 next 数组的信息，跳过一部分不必要的匹配。通过回退 j 的值，可以避免重新比对已经比较过的字符。

时间复杂度：

构建 next 数组的时间复杂度是 O(m)，其中 m 是 needle 的长度。
匹配过程中，haystack 字符串的遍历也只需要一次，因此总的时间复杂度是 O(n + m)，其中 n 是 haystack 字符串的长度，m 是 needle 字符串的长度。

代码

class Solution {// strStr 方法用于查找 haystack 中首次出现 needle 的位置public int strStr(String haystack, String needle) {// 通过 KMP 算法查找匹配位置int ans = 0;ans = kmp(haystack, needle);return ans;}// getNext 方法用于构建 needle 字符串的 next 数组public void getNext(int[] next, String s) {int j = -1; // j 表示当前的匹配位置next[0] = j; // next[0] 设为 -1，表示没有匹配for (int i = 1; i < s.length(); i++) {// 不匹配时，回退while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {j = next[j]; // 利用 next 数组的信息进行回退}// 匹配时，扩展 jif (s.charAt(i) == s.charAt(j + 1)) {j++;}next[i] = j; // 更新 next 数组}}// kmp 方法用于执行 KMP 算法，查找 t 字符串中首次出现 s 字符串的位置public int kmp(String t, String s) {int[] next = new int[s.length()]; // next 数组用于记录部分匹配信息getNext(next, s); // 调用 getNext 函数构建 next 数组int j = -1; // j 用于记录 needle 匹配的位置for (int i = 0; i < t.length(); i++) {// 当字符不匹配时，回退 jwhile (j >= 0 && t.charAt(i) != s.charAt(j + 1)) {j = next[j]; // 利用 next 数组的信息进行回退}// 匹配时，扩展 jif (t.charAt(i) == s.charAt(j + 1)) {j++;}// 如果 j 达到了 needle 的末尾，表示匹配成功if (j == s.length() - 1) {return i - s.length() + 1; // 返回匹配起始位置}}// 如果未找到匹配项，返回 -1return -1;}
}

459.重复的子字符串

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

示例 1:
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba"
输出: false
示例 3:
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
提示：

1 <= s.length <= 104
s 由小写英文字母组成

原理

1. KMP 部分匹配表（Next 数组）：

next[i] 存储的是字符串 s[0...i] 的最长相同前后缀的长度。具体来说，next[i] 表示在 s[0...i] 的字符串中，前后缀最长的公共部分的长度。

举个例子，假设字符串 s = "abab"：

对于字符 s[0] 到 s[3]，最长的前后缀是 "ab"，因此 next[3] 就是 1（前后缀长度为 1）。
next 数组记录了 s 中每个位置的最长前后缀信息。

2. KMP 算法的应用：

在 repeatedSubstringPattern 方法中，通过构建 next 数组来找到 s 字符串的 最长相同前后缀。

next[s.length() - 1] 是字符串 s 的最后一个字符的部分匹配值，它表示 s[0...s.length()-1] 的最长相同前后缀长度。我们通过 next[s.length() - 1] 得到 num，即该字符串的最长相同前后缀的长度。

例如：

对于字符串 "abab"，next[3] = 1，表示最长前后缀长度为 1。于是 num = 1。

3. 判断是否可以由重复子串构成：

判断字符串是否可以通过某个子串重复多次构成的关键是：若一个字符串可以被重复某个子串多次组成，那么这个子串的长度应该是 s.length() - num，即去除掉最大相同前后缀的部分，剩下的部分即为重复的子串。

如果 s.length() % (s.length() - num) == 0，并且 num != 0，则说明 s 字符串的长度可以被该子串的长度整除，且该子串不为空，这就意味着 s 可以由某个子串重复构成，返回 true。

反之，如果条件不满足，则返回 false，说明字符串不能由重复子串构成。

4. 复杂度分析：

构建 next 数组的时间复杂度是 O(n)，其中 n 是字符串 s 的长度。
判断条件是否满足的操作是常数时间操作，因此总的时间复杂度是 O(n)。

代码

class Solution {// repeatedSubstringPattern 方法用于判断字符串 s 是否可以通过重复子串构成public boolean repeatedSubstringPattern(String s) {// 构建 KMP 算法的 next 数组int[] next = new int[s.length()];getNext(next, s);// 计算最长相同前后缀长度int num = next[s.length() - 1] + 1;// 判断字符串的长度是否能被子串的长度整除，并且该子串不为空if (s.length() % (s.length() - num) == 0 && num != 0) {return true; // 说明可以通过重复子串构成} else {return false; // 否则不可以}}// getNext 方法用于构建 KMP 算法的 next 数组public void getNext(int[] next, String s) {int j = -1; // j 用于记录当前匹配的字符位置next[0] = j; // next[0] 表示没有匹配for (int i = 1; i < s.length(); i++) {// 当字符不匹配时，通过 next 数组的值进行回退while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {j = next[j];}// 匹配成功，扩展 jif (s.charAt(i) == s.charAt(j + 1)) {j++;}next[i] = j; // 更新 next 数组}}
}