最近发生了许多事，感觉自己最初的选择出现了非常大的问题，懊恼但无济于事，以后也不知道会怎么样。。。没事刷了刷leetcode，遇到了一个非常棒的解决思路，叹为观止。

题目

今天在leetcode上遇到了一个非常有意思的题459. Repeated Substring Pattern。

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

思路

这个题的题干是很简单的，就是判断已给字符串是否可以由一个子串重复组成，返回一个布尔值。

(1)常见的解决思路即尝试所有可能的子字符串。

(2)但还有一个rsrs3写的Easy python solution with explaination解法，一种递推的思路（感觉有点像线性代数里证明向量组的线性相关）。

非常的精彩！Very Amazing！上面链接的文章里有解法的详细的叙述与证明。

简而言之

Basic idea:

  • First char of input string is first char of repeated substring
  • Last char of input string is last char of repeated substring
  • Let S1 = S + S (where S in input string)
  • Remove 1 and last char of S1. Let this be S2
  • If S exists in S2 then return true else false
  • Let i be index in S2 where S starts then repeated substring length i + 1 and repeated substring S[0: i+1]

Let’s say T = S + S.

“S is Repeated => From T[1:-1] we can find S” is obvious.

即只要我们在T[1:-1]中可以找到S，S便为重复的。

下面是关于这句话的证明的翻译：

  • 如果在T[1:-1]中可以找到S，且index为p-1, 那么在T和S中的index为p

  • 令s1 = S[:p], S可以被表示为s1X1, 因为S为重复字符串，所以S = X1s1 = s1X1 (A)

    1. len(X1) < len(s1)
      这种情况不存在，以为如果我们发现S在T[1:-1]，则index应为len(X1)，而不是len(s1) = p

    2. len(X1) == len(s1)
      由A式可以推出X1 = s1，则S为重复的

    3. len(X1) > len(s1)
      因为A式，X1有前缀s1，可以表示为s1X2
      X1 = s1X2，由A式得到s1s1X2 = s1X2s1, 即X2s1 = s1X2 (B)
      这下就简洁明了了，依照前面的步骤递推，最终我们可以得到一个Xn，len(Xn) == len(s1) 并且 Xns1 = s1Xn => Xn = s1 => S = s1X1 = s1s1X2 = ... = s1s1...s1Xn-1 = s1s1...s1s1Xn => S is Repeated.

Python代码

1、常见思路（尝试所有可能的子字符串）

1
2
3
4
5
6
7
8
9
10
def repeatedSubstringPattern(self, s):
    n = len(s)
    d = 1
    while d * d <= n:
        if n % d == 0:
            for m in {d, n/d}:
                if m > 1 and m * s[:n/m] == s:
                    return True
        d += 1
    return False

2、非常精彩简洁

1
2
3
4
5
6
def repeatedSubstringPattern(self, str):
        if not str:
            return False
            
        ss = (str + str)[1:-1]
        return ss.find(str) != -1