移动匹配
解题思路
字符串 str 为 abcabc 是由两个 abc 子串组成；
此时我们将两个 str 拼接到一起变成了 abcabcabcabc 字符串，第一个 str 的后半部分 和 第二个 str 的前半部分 会组成一个新的 str；
这个时候再去掉这个字符串的前后两个字符后，这个字符串 str’ 就只能匹配一个中间的 str 了，如果是这样，那么只要判断 str‘ 是否包含 str 就可知是否由它的一个子串重复多次构成；
实现代码
var repeatedSubstringPattern = function (s) {
let str = s + s;
return str.slice(1, str.length - 1).includes(s);
};
KMP 算法
解题思路
前置知识 KMP 算法；
略
复杂度
-
时间复杂度：
O(n)，n 为字符串的长度； -
空间复杂度：
O(n)，构建了 next 数组；
实现代码
var repeatedSubstringPattern = function (s) {
if (s.length === 0) return false;
let next = getNext(s);
return next[next.length - 1] !== 0 && s.length % (s.length - next[next.length - 1]) === 0;
};
const getNext = (needle) => {
const next = [0];
let j = 0;
for (let i = 1; i < needle.length; i++) {
while (j > 0 && needle[i] !== needle[j]) {
j = next[j - 1];
}
if (needle[i] === needle[j]) {
j++;
}
next[i] = j;
}
return next;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 28. 找出字符串中第一个匹配项的下标
上一篇
评论
