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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。