Repeated Substring Pattern,LeetCode,459

题目描述：

给定一个非空的字符串 s，检查它是否可以通过重复某个子串多次构成。你可以假设字符串 s 仅由小写英文字母组成，并且它的长度不会超过 10000。

示例：

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

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

解题思路：

1. 字符串拼接法：
   • 将字符串 s 拼接一遍，即形成 s + s。
   • 去掉拼接后的字符串的第一个字符和最后一个字符，形成新的字符串 new_s。
   • 检查原字符串 s 是否在 new_s 中出现。
   • 如果出现，则说明 s 可以通过重复某个子串多次构成。
2. 数学法：
   • 设字符串 s 的长度为 n。
   • 遍历所有可能的子串长度 i（从 1 到 n/2），检查 n 是否能被 i 整除。
   • 如果 n 能被 i 整除，则检查长度为 i 的子串是否能够通过重复构成原字符串 s。
   • 如果找到这样的子串，则返回 True；否则返回 False。

代码实现（字符串拼接法）：

class Solution: def repeatedSubstringPattern(self, s: str) -> bool: if not s: return False

    new_s = (s + s)[1:-1]
    return s in new_s

代码实现（数学法）：

class Solution: def repeatedSubstringPattern(self, s: str) -> bool: n = len(s) for i in range(1, n // 2 + 1): if n % i == 0: substring = s[:i] if substring * (n // i) == s: return True return False

解释：

1. 字符串拼接法：
   • new_s = (s + s)[1:-1] 的目的是去掉拼接后的字符串的首尾字符，避免直接包含原字符串。
   • s in new_s 检查原字符串是否在新字符串中出现，如果出现则说明可以通过重复某个子串构成。
2. 数学法：
   • n % i == 0 检查 n 是否能被 i 整除，确保子串长度 i 是 n 的因数。
   • substring = s[:i] 提取长度为 i 的子串。
   • substring * (n // i) == s 检查通过重复子串 substring 是否能构成原字符串 s。

复杂度分析：

• 字符串拼接法：
  • 时间复杂度：O(n)，其中 n 是字符串的长度。
  • 空间复杂度：O(n)，因为生成了新的字符串 new_s。
• 数学法：
  • 时间复杂度：O(n * sqrt(n))，最坏情况下需要遍历所有可能的子串长度，并检查子串的重复构成。
  • 空间复杂度：O(1)，只使用了常数额外空间。

这两种方法各有优缺点，字符串拼接法实现简单且效率较高，而数学法更直观地展示了问题的本质。根据实际情况选择合适的方法即可。