问题描述

---

思路分析

1. 核心问题拆解

• 给定一个字符串 inp，如果可以通过一个较短的子串多次拼接生成，则满足题目要求。
• 如果找不到满足条件的子串，则输出空字符串。

2. 关键观察

1. 字符串长度特性：
   • 如果一个字符串是由某个子串重复拼接而成，那么字符串的长度一定可以被该子串的长度整除。
   • 比如：
     • “abababab” 长度为 8，可能的子串长度为 1、2、4。
     • “abcabcabcabc” 长度为 12，可能的子串长度为 1、2、3、4、6。
2. 子串的重复验证：
   • 假设子串长度为 len，则取字符串的前 len 个字符作为子串 subStr。
   • 用该子串重复拼接，形成一个新字符串：
     • 如果这个新字符串与原字符串一致，则 subStr 为最短子串。
     • 如果不一致，继续尝试下一个可能的子串长度。
3. 边界条件：
   • 如果字符串长度为 1，例如 “a”，没有任何子串可以重复生成，因此输出空字符串。
   • 如果字符串本身不能通过任何子串重复生成（例如 “abc”），也需要返回空字符串。

3. 算法流程

1. 获取字符串长度 n。
2. 遍历所有可能的子串长度 len，范围为 1 到 n/2（因为子串长度不会超过字符串长度的一半）。
3. 对于每个可能的子串长度 len：
   • 检查 n % len == 0（子串长度必须整除字符串长度）。
   • 提取前 len 个字符作为候选子串 subStr。
   • 用 subStr 反复拼接，生成新字符串：
     • 如果新字符串与原字符串相等，返回 subStr。
4. 如果遍历结束没有找到满足条件的子串，返回空字符串。

---

参考代码（Java）

public class Main {
    public static String solution(String inp) {
        int n = inp.length();

        // 遍历可能的子串长度
        for (int len = 1; len <= n / 2; len++) {
            // 只有当字符串长度能被len整除时才可能是重复子串
            if (n % len == 0) {
                String subStr = inp.substring(0, len); // 取前len个字符作为子串
                StringBuilder sb = new StringBuilder();

                // 构造由子串重复组成的新字符串
                for (int i = 0; i < n / len; i++) {
                    sb.append(subStr);
                }

                // 如果新字符串与原字符串相等，则找到最短子串
                if (sb.toString().equals(inp)) {
                    return subStr;
                }
            }
        }

        // 如果没有找到，返回空字符串
        return "";
    }

    public static void main(String[] args) {
        System.out.println(solution("abcabcabcabc").equals("abc")); 
        System.out.println(solution("abababab").equals("ab"));
        System.out.println(solution("abababac").equals(""));
        System.out.println(solution("a").equals(""));
    }
}

代码分析

1. 获取字符串长度

int n = inp.length();

• n 是字符串的长度，用于计算可能的子串长度以及重复次数。
• 举例：如果字符串 inp = "abababab"，则 n = 8。

2. 遍历可能的子串长度

for (int len = 1; len <= n / 2; len++) {

• 遍历可能的子串长度 len，范围是从 1 到 n / 2，因为子串长度不会超过字符串长度的一半。
• 如果 len 超过 n / 2，重复的子串就不可能存在。

3. 判断字符串长度是否能被子串长度整除

if (n % len == 0) {

• 只有当字符串长度 n 能被 len 整除时，才可能用一个长度为 len 的子串重复生成。
• 举例：
  • 如果 inp = "abababab"，n = 8，当 len = 1, 2, 4 时满足整除条件。
  • 如果 inp = "abcabcabcabc"，n = 12，当 len = 1, 2, 3, 4, 6 时满足整除条件。

4. 提取候选子串

String subStr = inp.substring(0, len);

• 从字符串的起始位置提取长度为 len 的子串，作为候选子串。
• 举例：
  • 如果 inp = "abababab"，len = 2，提取子串 subStr = "ab"。
  • 如果 inp = "abcabcabcabc"，len = 3，提取子串 subStr = "abc"。

5. 用子串构造新字符串

StringBuilder sb = new StringBuilder();

for (int i = 0; i < n / len; i++) {
    sb.append(subStr);
}

• 利用 StringBuilder 重复拼接 subStr，生成一个新字符串。
• 拼接次数为 n / len，因为一个长度为 len 的子串需要重复这么多次才能覆盖整个字符串。
• 举例：
  • 如果 inp = "abababab"，subStr = "ab"，重复 4 次，得到 sb = "abababab"。
  • 如果 inp = "abcabcabcabc"，subStr = "abc"，重复 4 次，得到 sb = "abcabcabcabc"。

6. 判断新字符串是否与原字符串相等

if (sb.toString().equals(inp)) {
    return subStr;
}

• 将 StringBuilder 拼接得到的新字符串与原字符串比较：
  • 如果相等，说明当前的子串 subStr 是最短重复子串。
  • 如果不相等，则继续尝试下一个可能的子串长度。
• 举例：
  • 对于 inp = "abababab"，subStr = "ab"，sb = "abababab"，相等，返回 "ab"。
  • 对于 inp = "abc"，len = 1 时，sb = "aaa"，不相等，返回空字符串。

7. 返回结果

return "";

• 如果遍历所有可能的子串长度后，仍未找到符合条件的子串，说明字符串无法通过某个子串重复生成，返回空字符串。

代码复杂度分析

1. 时间复杂度：

• 外层循环：可能的子串长度最多为 n/2，复杂度 O(n) 。
• 内层拼接：每次拼接最多需要 O(n) 的操作。
• 总复杂度为 O(n²) 。

1. 空间复杂度：

• 使用了 StringBuilder，拼接操作占用额外空间，但总体复杂度为 O(n) 。