题目描述

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

示例 1:

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

示例 2:

输入: s = “aba”
输出: false

示例 3:

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

提示：

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

解题思路

首先想到的是用暴力法，遍历所有可能的子串长度，然后检查是否可以通过重复该子串构成原字符串。具体实现时，可以从长度为 1 的子串开始，逐渐增加长度，直到字符串的一半。因为如果子串长度超过一半，就不可能重复构成原字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func repeatedSubstringPattern(s string) bool {
	for i := 1; i < len(s)/2+1; i++ {
		if len(s)%i != 0 {
			continue
		}
		flag := true
		for j := i; j <= len(s)-i; j += i {
			if s[:i] != s[j:j+i] {
				flag = false
				break
			}
		}
		if flag {
			return true
		}
	}

	return false
}

上面的代码中，做了一些情况的优化，比如如果字符串长度不能被子串长度整除，就直接跳过该长度的子串检查。这样可以减少不必要的比较。

这种方法的时间复杂度是 O(n^2)，但其实提交也能通过。

优化思路

看了题解后，发现还有一个思路，可以通过字符串的拼接来判断是否存在重复的子串。具体思路是将字符串 s 拼接成 s + s，然后去掉首尾各一个字符，检查剩下的字符串中是否包含原字符串 s。

1
2
3
func repeatedSubstringPattern(s string) bool {
    return strings.Contains(s[1:]+s[:len(s)-1], s)
}

要理解这种方法，就需要知道一个重要的性质：如果一个字符串是由重复子串构成的，那么将该字符串进行若干次移位后可以得到原字符串。例如，对于字符串 s = "abcabc"：将其移位后可以得到 "bcabca"、"cabcab"、"abcabc"。

基于这个思考，可以构建一个新的字符串 s + s，比如：s 为 abcabc，那么 s+s 为 "abcabcabcabc"。s 的所有移位都可以在这个新字符串中找到（bcabca、cabcab、abcabc）。当然 ss 是由两个 s 组成的，所以包含了 s 本身，如果去掉首尾各一个字符后，仍然能找到 s，那么就说明 s 是由重复子串构成的。

这种方法的时间复杂度是 O(n)，空间复杂度也是 O(n)。