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 {
           var str strings.Builder
           str.WriteString(s[:i])

           for len(str.String()) < l {
               str.WriteString(s[:i])
           }

           if str.String() == s {
               return true
           }
        }
    }

    return false
}

更漂亮的解法：

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
}