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

布满荆棘的人生 2023-01-18 04:07 148阅读 0赞

## 题目 ##

[https://leetcode-cn.com/problems/repeated-substring-pattern/][https_leetcode-cn.com_problems_repeated-substring-pattern]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 思路 ##

**暴力解法 + 剪枝优化**

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

假设子串的长度为 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;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode-cn.com_problems_repeated-substring-pattern]: https://leetcode-cn.com/problems/repeated-substring-pattern/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221021/fbed8da1bbb14a3182d6cc40265af5c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221021/fcc158ec07be474caf04499c6958f80f.png