459.md

Question:

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.)

Analysis

这里首先介绍一种比较直观，但比较费事的解法，就是首先建立一个字符的hash，来表征每个字符出现的位置：

例如， “abacabacabac” 建立好之后，就是：

{
  "a": [0 2 4 6 8 10],
  "b": [1 5 9],
  "c": [3 7 11]
}

之后，就可以通过位置分析了，选一个比较短的，如果可以的话，其他字符长度一定是它的整数倍，并且都各自是一个等差数列。一般情况都符合。但是，该方法也有局限性的，比如，遇到下面的就不行了：

"abaababaab"

因为a和b都存在一个单独出现的字符，子字符串中，a出现3次，b出现2次。失败，就是解法一。虽然失败，我还是把它写下来了，主要是通过hash来简化问题的方法还是可取的。

解法二就比较巧妙了，如果一个字符串可以由某个子串重复得来，那么这个子串的长度一定不会大于原来字符串长度的一半，那我们就从一半开始递减，直到1为止，如果某时找到这么一个子串，重复多次，可以和原来字符串相等，那就是了。

Tips

Code

// 解法一
func isContains(a []int, n int) bool {
        for _, v := range a {
                if n == v {
                        return true
                }
        }
        return false
}

func repeatedSubstringPattern(s string) bool {
        mapping := map[rune][]int{}
        for k, v := range s {
                if !isContains(mapping[v], k) {
                        mapping[v] = append(mapping[v], k)
                }
        }

        minLen := 0 // 找到一个出现次数最少的字母，以及它出现的次数
        var minKey rune
        for k, v := range mapping {
                if minLen == 0 || minLen > len(v) {
                        minLen = len(v)
                        minKey = k
                }
        }

        // 如果被选出的字母，只出现了一次的话，肯定不是了
        if minLen < 2 {
                return false
        }
           // 把这个选出的最小出现次数的字母作为模板，看看它是否符合等差数列，如果不符合，这个字符串肯定不符合
        list := mapping[minKey]
        diff := (list[minLen-1] - list[0]) / (minLen - 1)
        for i := 1; i < minLen; i++ {
                if list[i] != list[i-1]+diff {
                        return false
                }
        }

        for key, candidates := range mapping {
                if minKey == key {
                        continue
                }

                if len(candidates)%minLen != 0 {
                        return false
                }

                for i := 0; i < len(candidates)/minLen; i++ {
                        for j := i + len(candidates)/minLen; j < len(candidates); j += len(candidates) / minLen {
                                if candidates[j] != candidates[j-len(candidates)/minLen]+diff {
                                        return false
                                }
                        }
                }
        }
        return true
}

// 解法二
func repeatedSubstringPattern(s string) bool {
        for i := len(s) / 2; i >= 1; i-- {
                if len(s)%i != 0 {
                        continue
                }
                temp := ""
                for j := 0; j < len(s)/i; j++ {
                        temp += s[:i]
                }
                if temp == s {
                        return true
                }
        }

        return false
}