459. Repeated Substring Pattern 重复的子字符串

@TOC

[LeetCode]

• Difficulty: Easy

# 题目描述

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

# 解题方法

# 遍历子串

• 重复的子串的长度肯定是总长度的因子。
• 遍历所有的因子，从length/2开始
• 如果i是length的因子，把从0到i这个substring重复length()/i倍
• 看看这个重复后的串是否与原来的串相等。
``````public class Solution {
public boolean repeatedSubstringPattern(String str) {
int l = str.length();
for(int i=l/2;i>=1;i--) {
if(l%i==0) {
int m = l/i;
String subS = str.substring(0,i);
StringBuilder sb = new StringBuilder();
for(int j=0;j<m;j++) {
sb.append(subS);
}
if(sb.toString().equals(str)) return true;
}
}
return false;
}

}
``````

AC: 48 ms

``````class Solution:
def repeatedSubstringPattern(self, s):
"""
:type s: str
:rtype: bool
"""
len_s = len(s)
for i in range(1, len_s // 2 + 1):
if len_s % i == 0:
sub_s = s[:i]
if sub_s * (len_s // i) == s:
return True
return False
``````

# 日期

2017 年 1 月 15 日 2018 年 7 月 4 日 2018 年 11 月 22 日 —— 感恩节快乐～