LeetCode刷题记录:(4)重复的子字符串
2024-01-10 14:08:24
leetcode传送通道
/**
重复字符串的next数组是有规律的
abcabc:-1 0 0 0 1 2
abcabcabc:-1 0 0 0 1 2 3 4 5
abcabcabcabc:-1 0 0 0 1 2 3 4 5 6 7 8
abcabcabcabg:-1 0 0 0 1 2 3 4 5 6 7 8 欸嘿,和上面一样,怎么处理?简单,判断一下末尾字符和子串末尾字符是否一样就可以了
*/
根据next数组,一行 if 判断语句就可以搞定
更加详细一些的next数组说明看这里,也不长
class Solution {
public boolean repeatedSubstringPattern(String s) {
int next[] = getNext(s);
int L = s.length(); //s的长度 即 next数组长度L
int subL = L - (next[L-1]+1); //最小子串长度subL = L - next数组末尾元素 (重复串才会满足)
if(L>1 && L % subL == 0 && s.charAt(L-1) == s.charAt(subL-1)){
return true;
}else{
return false;
}
}
private int[] getNext(String s){
int[] next = new int[s.length()];
next[0] = -1;
int j = -1, i = 0;
while(i<s.length()-1){
if(j==-1 || s.charAt(i)==s.charAt(j)){
next[++i] = ++j;
}else{
j = next[j];
}
}
return next;
}
}
文章来源:https://blog.csdn.net/weixin_45606831/article/details/135498812
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!