题目地址：https://leetcode.com/problems/repeated-substring-pattern/open in new window
- 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;
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
AC:48 ms二刷，python.
现在再刷这个题的时候因为用的Python，已经对字符串处理了然于胸了，所以很快就写出了下面的答案：
同样是遍历因子，然后把新的切片乘以倍数，看得到的字符串是否和源字符串相同。
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
1 2 3 4 5 6 7 8 9 10 11 12 13
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发