題目
Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.
Example 1:
Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.
Example 2:
Input: "aba"
Output: False
Example 3:
Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)
解題思路
假設(shè)輸入字符串長度為lenS， 則所求字串長度范圍1 <= lenSub <= lenS/2, 并且滿足
lenS % lenSub == 0
在子串范圍1 <= lenSub <= lenS/2內(nèi)對每個子串進(jìn)行判斷啊奄，
- 首先判斷是否滿足 lenS % lenSub == 0
- 若滿足侦锯，則將輸入字符串分為多個長度為lenSub的子串瓜浸，如果所有子串都和第一個子串相等讯柔，則說明該子串就是要找的子串钓觉，否則不是要找的子串
- 如果遍歷完所有的子串都不滿足衔蹲，則返回false
代碼
func repeatedSubstringPattern(s string) bool {
lenS := len(s)
for i := 1; i <= lenS/2; i++ {
if lenS % i != 0 {
continue
}
var notRepeat bool
sub := s[:i]
for j := i; j <= lenS - i; j = j+i {
if s[j:j+i] != sub {
notRepeat = true
fmt.Printf("sub:%+v, sj:%+v\n", sub, s[j:j+i])
break
}
}
if !notRepeat {
return true
}
}
return false
}
