leetcode_字符串 459. 重复的子字符串

459. 重复的子字符串

• 给定一个非空的字符串s，检查是否可以通过由他的一个子串重复多次构成
• 思路：
  1. 首先判断字符串s是否为空或长度是否为1，若满足这两种条件，则说明不存在子字符串，返回False
  2. 遍历所有可能的子串（从长度为1的子串开始遍历）
  3. 如果存在子串a使得len(s)能够整除len(a)，则说明该子串a有可能重复多次后能够成为s
  4. 将子串a重复多次直至和字符串s等长，判断是否相等，相等返回True，否则返回False

def func(s):if not s or len(s) == 1:# 若字符串为空，返回Falsereturn Falsefor i in range(1, len(s)):# 遍历所有可能的子串长度if len(s) % i == 0:# 如果 s 的长度可以被 i 整除a = s[:i]# 从字符串 s 中提取长度为 i 的子串if a * (len(s) // i) == s:# 不断重复子串a直到长度为len(s)return Truereturn Falseprint(func("abab"))

• 时间复杂度： O(n^2)，其中n为字符串s的长度
  • 最坏的情况下，当 i 接近 n 时，子串提取操作需要 O(n)，并且比较操作也是 O(n)，总的时间复杂度为O(n^2)
• 空间复杂度： O(n)