459. Repeated Substring Pattern

Easy
Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
Example 1:
Input: s = "abab"
Output:
true
Explanation:
It is the substring "ab" twice.
Example 2:
Input: s = "aba"
Output:
false
Example 3:
Input: s = "abcabcabcabc"
Output:
true
Explanation:
It is the substring "abc" four times or the substring "abcabc" twice.
Constraints:
  • 1 <= s.length <= 104
  • s consists of lowercase English letters.

解題

遍歷 s 字串,如果字串可以整除目前的位置+1也就是目前的長度,進入check function做檢查。
func repeatedSubstringPattern(s string) bool {
length := len(s)
for i:=0; i<len(s)-1; i++ {
if length%(i+1)==0 {
if check(s, i+1) {
return true
}
}
}
return false
}
func check(s string, l int) bool {
for i:=0; i<l; i++ {
for j:=i; j<len(s); j = j+l {
if s[j]!=s[i] {
return false
}
}
}
return true
}g
另一個解法,與上方程式碼不同之處在使用 strings.Repeat 函數建構出完整的字串,再和 s 做比較。
func repeatedSubstringPattern(s string) bool {
l := len(s)
for i := 1; i <= l/2; i++ {
if l%i == 0 && strings.Repeat(string(s[:i]), l/i) == s {
return true
}
}
return false
}