459. 重复的子字符串

leetcode链接:
https://leetcode.cn/problems/repeated-substring-pattern/

题目分析

字符串题目,优先考虑KMP算法。

方案一

KMP算法,

首先想到的思考思路。

然后在运行过程中出现报错,为此,重新分析解题,如下图所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public boolean repeatedSubstringPattern(String s) {
int[] countNext = CountNext(s);
int i= 0 , j = 0, end = 0;

for (i = 1; i < s.length(); i++) {
// 判断新的字符是否等于所指向的字符。相等,则对j进行移位操作
if (s.charAt(i) == s.charAt(j)) {
// 当j走到循环体的末尾时,将数值进行初始化,否则具体向后走
if (j == end) {
if (i == (s.length() - 1)) {
return true;
}
j = 0;
} else {
j++;
}
} else { // 此时当前的char与j位置的char不同,需要对相关数据进行处理
j = countNext[i];
end = i - countNext[i];
}
}

return false;
}

public int[] CountNext(String s) {
int[] result = new int[s.length()];
int j = 0;

for (int i = 1; i < s.length(); i++) {
while (j > 0 && s.charAt(i) != s.charAt(j)) {
j = result[--j];
}

if (s.charAt(i) == s.charAt(j)) {
result[i] = ++j;
}
}
return result;
}
}

结果

解答成功:
执行耗时:15 ms,击败了48.69% 的Java用户
内存消耗:43.2 MB,击败了8.10% 的Java用户

分析

时间复杂度:
O( n )

空间复杂度:
O( n )

官方题解

https://leetcode.cn/problems/repeated-substring-pattern/solution/zhong-fu-de-zi-zi-fu-chuan-by-leetcode-solution/

方法一、字符串匹配

1
2
3
4
5
6
7
8
9
10
class Solution {
public boolean repeatedSubstringPattern(String s) {
return (s + s).indexOf(s, 1) != s.length();
}
}

作者:LeetCode-Solution
链接:https://leetcode.cn/problems/repeated-substring-pattern/solution/zhong-fu-de-zi-zi-fu-chuan-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法二、优化的 KMP 算法

官网:
https://leetcode.cn/problems/repeated-substring-pattern/solution/zhong-fu-de-zi-zi-fu-chuan-by-leetcode-solution/

代码随想录中相关数据参考:
https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html#kmp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public boolean repeatedSubstringPattern(String s) {
return kmp(s);
}

public boolean kmp(String pattern) {
int n = pattern.length();
int[] fail = new int[n];
Arrays.fill(fail, -1);
for (int i = 1; i < n; ++i) {
int j = fail[i - 1];
while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
j = fail[j];
}
if (pattern.charAt(j + 1) == pattern.charAt(i)) {
fail[i] = j + 1;
}
}
return fail[n - 1] != -1 && n % (n - fail[n - 1] - 1) == 0;
}
}

作者:LeetCode-Solution
链接:https://leetcode.cn/problems/repeated-substring-pattern/solution/zhong-fu-de-zi-zi-fu-chuan-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

459. 重复的子字符串
http://yuanql.top/2023/06/16/02_leetcode/459. 重复的子字符串/
作者
Qingli Yuan
发布于
2023年6月16日
许可协议