Easy

题目描述

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

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成 (或子串 "abcabc" 重复两次构成)。

提示:

  • 1 <= s.length <= 10^4
  • s 由小写英文字母组成

解题思路

这道题要判断一个字符串是否由某个子串重复构成。有几种解法：

方法一：字符串拼接法（推荐） 核心思想是：如果字符串 s 由某个子串重复构成，那么将两个 s 拼接后去掉首尾字符，原字符串 s 一定会在其中出现。例如 s = "abab"，拼接后得到 "abababab"，去掉首尾得到 "bababa"，原串 "abab" 确实在其中。

方法二：枚举子串长度 枚举所有可能的子串长度（必须是 n 的因子），检查是否能由该长度的子串重复构成。时间复杂度较高但思路直观。

方法三：KMP算法 利用 KMP 算法中的 next 数组特性，如果 n % (n - next[n-1]) == 0 且 next[n-1] != 0，则存在重复模式。

字符串拼接法最简洁高效，是面试中的最佳选择。

代码实现

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string doubled = s + s;
        return doubled.substr(1, doubled.length() - 2).find(s) != string::npos;
    }
};

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return s in (s + s)[1:-1]

public class Solution {
    public bool RepeatedSubstringPattern(string s) {
        string doubled = s + s;
        return doubled.Substring(1, doubled.Length - 2).Contains(s);
    }
}

var repeatedSubstringPattern = function(s) {
    return (s + s).slice(1, -1).includes(s);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
字符串拼接法O(n)O(n)
枚举子串长度O(n√n)O(1)
KMP算法O(n)O(n)

相关题目