问题描述

给定一个非空的字符串 s，检查是否可以通过由它的一个子串重复多次构成。

解题思路

如果字符串 s 可以由子串 p 重复 k 次构成，那么 s 的长度 n 必定是子串长度 len(p) 的整数倍，即 len(p) 是 n 的因数。

因数枚举法

  1. 找出所有可能的子串长度：

    • 一个子串如果可以重复构成整个字符串，其长度必然是字符串总长度 n 的一个因数
    • 遍历 1 到 n/2，收集所有 n 的因数（子串长度不可能超过 n/2，因为至少要重复两次）

  2. 逐个验证：

    • 对于每个因数 factor（可能的子串长度）：
      • 计算重复次数 count = n / factor
      • 截取前 factor 个字符作为候选子串 sub
      • 使用 sub.repeat(count) 生成重复字符串，与原始字符串 s 比较
      • 如果相等，返回 true

  3. 返回结果：如果所有因数都无法匹配，返回 false。

举例说明

以输入 s = "abab"（n=4）为例：

  • 因数有：[1, 2]
  • 检查 factor=1：sub = "a"，重复 4 次得 "aaaa" ≠ "abab"，不匹配
  • 检查 factor=2：sub = "ab"，重复 2 次得 "abab" = "abab"，匹配，返回 true

以输入 s = "abcabcabc"（n=9）为例：

  • 因数有：[1, 3]（4 不是因数，跳过）
  • factor=1："a" 重复 9 次 ≠ 原串
  • factor=3："abc" 重复 3 次 = 原串，返回 true

为什么枚举因数可行？

如果子串长度不是总长度的因数，则无论如何重复都无法正好拼接成原字符串。因此只需要检查所有因数长度的子串即可覆盖所有可能的解，这是一种高效的剪枝策略。

复杂度分析

  • 时间复杂度：O(n * d(n))，其中 d(n) 是 n 的因数个数。对于每个因数，需要进行一次字符串拼接和比较，耗时 O(n)。在最坏情况下 d(n) 约等于 O(√n)，总时间复杂度约为 O(n√n)。
  • 空间复杂度：O(n)，需要存储拼接后的字符串进行比较。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package code.J459;

import java.util.ArrayList;
import java.util.List;

public class J459 {
    private List<Integer> findFactor(int num) {
        List<Integer> factor = new ArrayList<>();
        for (int i = 1; i <= num / 2; i++) {
            if (num % i == 0) factor.add(i);
        }
        return factor;
    }

    public boolean repeatedSubstringPattern(String s) {
        int sLen = s.length();
        List<Integer> factors = findFactor(sLen);
        for (Integer factor : factors) {
            int count = sLen / factor;
            String sub = s.substring(0, factor);
            if (sub.repeat(count).equals(s)) return true;
        }
        return false;
    }
}