459. Repeated Substring Pattern

题目描述和难度

  • 题目描述:

给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。

示例 1:

输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。

示例 2:

输入: "aba"

输出: False

示例 3:

输入: "abcabcabcabc"

输出: True

解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

思路分析

求解关键:依据题目的要求,逐个进行判断就可以了。

1、首先分析出重复单元的长度最小是 1 ,最大是 len/2(向下取整);
2、如果字符串长度不能整除重复单元的长度,这一轮循环就可以跳过了;
3、接着就是比较,解法 1 是我的写法,解法 2 是从讨论区看来的,利用了求模运算;
4、解法 3 也是从讨论区看来的,比较巧妙,非常简洁。

参考解答

参考解答1

public class Solution {

    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        if (len < 2) {
            return false;
        }
        for (int i = 1; i <= len / 2; i++) {
            // 只有字符串长度整除重复单元的长度的时候,才有必要继续做判断
            if (len % i == 0) {
                // 第 1 个重复单元的字符串
                String template = s.substring(0, i);
                // 每一轮内层循环都假设能找到,只要有一个不匹配,这个值就会被置为 false,然后退出内层循环
                boolean found = true;
                // 注意:substring 的第 2 个参数是右边端点,取不到
                for (int j = i; j + i <= len; j += i) {
                    String segment = s.substring(j, j + i);
                    if (!template.equals(segment)) {
                        found = false;
                        break;
                    }
                }
                // 遍历完整个字符串,都没有将 found 改为 false,就说明,该字符串符合题意,存在性成立,可以直接返回
                if (found) {
                    return true;
                }
            }
        }
        // 存在性问题,如果全部都判断完毕都不能返回 true,就得返回 false
        return false;
    }
}

参考解答2

public class Solution {

    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        if (len < 2) {
            return false;
        }
        // 5 到 2 为止 0,1,2,3,4
        // 6 到 3 为止 0,1,2,3,4,5
        // 7 到 3 为止 0,1,2,3,4,5,6
        // i 表示重复单元的长度
        for (int i = 1; i <= len / 2; i++) {
            // 如果不能被重复单元整除,那么也就不符合题意
            if (len % i != 0) {
                continue;
            }
            int j = i;
            // 下面这个逻辑判断是关键
            while (j < len && s.charAt(j) == s.charAt(j % i)) {
                j++;
            }
            if (j == len) {
                // 如果存在就马上返回
                return true;
            }
        }
        // 存在性问题,如果全部都判断完毕,就得返回 false
        return false;
    }

    public static void main(String[] args) {
        String s = "abab";
        Solution solution = new Solution();
        boolean repeatedSubstringPattern = solution.repeatedSubstringPattern(s);
        System.out.println(repeatedSubstringPattern);
    }
}

参考解答3

public class Solution {

    public boolean repeatedSubstringPattern3(String s) {
        // 重复一次,掐头去尾,只要包含就可以了
        return ((s + s).substring(1, 2 * s.length() - 1).contains(s));
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0459-repeated-substring-pattern ,如果我的题解有错误,或者您有更好的解法,欢迎您告诉我 liweiwei1419@gmail.com