leetcode 459. 重复的子字符串（Java版）-蒲公英云

leetcode 459. 重复的子字符串（Java版）

题目

https://leetcode-cn.com/problems/repeated-substring-pattern/
在这里插入图片描述

思路

暴力解法 + 剪枝优化

经过尝试，如果直接使用暴力解法会超时，于是想到了一种剪枝的方式：

假设子串的长度为 step，原串的长度为 length。从直观上来看，原串的长度必然为子串长度的倍数，即，只有当 length%step==0 时，才有可能成为正确的子串。根据这个结论，进行剪枝优化。

代码

评论区说，简单题就是暴力解能通过的题。本文用的暴力解，优化之后才勉强 AC。

class Solution { 
    public static boolean repeatedSubstringPattern(String s) { 
        char[] charArray = s.toCharArray();
        int step = 0;
        while (step < s.length() / 2) { // 遍历每个步长
            step++;
            // 剪枝优化
            while (charArray.length % step != 0) { 
                step++;
            }
            // 当前步长是否能匹配
            int i, j;
            for (i = 0, j = 0; i < charArray.length; i++, j++) { 
                j %= step;
                if (charArray[i] != charArray[j]) break;
            }
            if (i == charArray.length && charArray.length % step == 0 && step < s.length()) { 
                return true;
            }
        }
        return false;
    }
}