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++) { if (s.charAt(i) == s.charAt(j)) { if (j == end) { if (i == (s.length() - 1)) { return true; } j = 0; } else { j++; } } else { 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) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
|
方法二、优化的 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) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
|