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:

1
2
3
4
5
Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

Example 2:

1
2
3
Input: "aba"
Output: False

Example 3:

1
2
3
4
5
Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

思路

需要注意,不能利用string里面元素出现的个数来进行判断。比如说对于“abba”这样的情况,统计元素出现个数是不恰当的。

还是采用最直接的方法,首先判断子数组的长度能不能被整体数组的长度整除;接下来判断这个子数组是否符合题意,由此得到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class (object):
def repeatedSubstringPattern(self, str):
"""
:type str: str
:rtype: bool
"""
length = len(str)
for i in range(1,length+1):
if (length % i == 0):
iter = length / i
for j in range(1,iter):
if (str[0:i] != str[(i*j):(i*(j+1))]):
break
if (j == iter-1):
return True
return False