問題描述

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

補(bǔ)充說明：

這個(gè)題目的要求大概是這個(gè)樣子的：給定你一個(gè)非空字符串，去判斷它不是不由它的子串成倍出現(xiàn)構(gòu)成的。例如：“abcabc”是它的子串“abc”重復(fù)兩次構(gòu)成的。

方案分析

1. 看到這個(gè)題目，首先想到的是如何確定它的子串，筆者瞬間想到的是將這個(gè)字符串先二分，然后判定是否兩個(gè)子串是否相同，相同則返回true，否則進(jìn)行三分，然后判定三個(gè)子串是否相同，以此類推，直到按長(zhǎng)度劃分。
2. 這個(gè)方法可行，但是實(shí)現(xiàn)起來略微復(fù)雜，并且時(shí)間超過了leetcode的限制，不是一個(gè)好的代碼，貼出來僅供參考。

python實(shí)現(xiàn)

class Solution(object):
    def repeatedSubstringPattern(self, str):
        """
        :type str: str
        :rtype: bool
        """
        def split(str, width):
            res = []
            start = 0
            while (start + width < len(str)):
                res.append(str[start:start + width])
                start += width
            res.append(str[start:])
            return res

        for i in range(1, len(str)):
            split_list = split(str, i)
            import collections
            dict = collections.Counter(split_list)
            if len(dict) == 1:
                return True
            else:
                continue
        return False

方案分析2

1. python字符串有個(gè)特性，簡(jiǎn)述就是‘a(chǎn)’ * 3 = 'aaa'，想必這個(gè)大家都不陌生吧，筆者看到有人利用這個(gè)特性實(shí)現(xiàn)了這個(gè)功能。
2. 原理是，先提取字符串的一半，然后乘以2，看生成串和原串是否相同，相同則true，否則提取字符串三分之一，然后乘以3，以此類推。其實(shí)思路和上面大同小異，但是利用python的這個(gè)特性省去了好多麻煩，還縮短了運(yùn)行時(shí)間。

python實(shí)現(xiàn)2

class Solution(object):
    def repeatedSubstringPattern(self, str):
        """
        :type str: str
        :rtype: bool
        """
        if not str or len(str) < 2:
            return False

        strlen = len(str)
        pos = strlen / 2
        while pos > 0:
            if strlen % pos == 0:
                substr = str[:pos]
                divisor = strlen / pos
                if substr*divisor == str:
                    return True
            pos -= 1
        return False

方案分析3

1. 有人一做字符串運(yùn)算，就想到了正則表達(dá)式，ok，確實(shí)可行。不解釋，直接借用別人的代碼。

python實(shí)現(xiàn)3

def repeatedSubstringPattern(self, str):
    """
    :type str: str
    :rtype: bool
    """
    import re
    return bool(re.match(r"^([a-z]+)\1+$", str))

方案分析4

1. 一不小心看到一個(gè)更牛的解決思路，筆者腦子是不夠用，連簡(jiǎn)單的都想不到，不用說這位大神的想法了。下面給翻譯大神的思路。

輸入字符串的第一個(gè)字符串是重復(fù)子字符串的第一個(gè)字符

輸入字符串的最后一個(gè)字符串是重復(fù)子字符串的最后一個(gè)字符

令S1 = S + S（其中輸入字符串中的S）

刪除S1的第一個(gè)和最后一個(gè)字符，生成字符串S2。

如果S存在于S2中，則返回true否則為false。

3. 這個(gè)思想的精髓就在于通過拷貝一次字符串，并且各自破壞一小部分，然后通過兩個(gè)串的拼接完成原串的查找。如果串不滿足要求的特性，是拼裝不出來的。

python實(shí)現(xiàn)4

def repeatedSubstringPattern(self, str):

        """
        :type str: str
        :rtype: bool
        """
        if not str:
            return False

        ss = (str + str)[1:-1]
        return ss.find(str) != -1