问题描述
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.)
补充说明：
这个题目的要求大概是这个样子的：给定你一个非空字符串，去判断它不是不由它的子串成倍出现构成的。例如：“abcabc”是它的子串“abc”重复两次构成的。
方案分析
- 看到这个题目，首先想到的是如何确定它的子串，笔者瞬间想到的是将这个字符串先二分，然后判定是否两个子串是否相同，相同则返回true，否则进行三分，然后判定三个子串是否相同，以此类推，直到按长度划分。
- 这个方法可行，但是实现起来略微复杂，并且时间超过了leetcode的限制，不是一个好的代码，贴出来仅供参考。
python实现
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
- python字符串有个特性，简述就是‘a’ * 3 = 'aaa'，想必这个大家都不陌生吧，笔者看到有人利用这个特性实现了这个功能。
- 原理是，先提取字符串的一半，然后乘以2，看生成串和原串是否相同，相同则true，否则提取字符串三分之一，然后乘以3，以此类推。其实思路和上面大同小异，但是利用python的这个特性省去了好多麻烦，还缩短了运行时间。
python实现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
- 有人一做字符串运算，就想到了正则表达式，ok，确实可行。不解释，直接借用别人的代码。
python实现3
def repeatedSubstringPattern(self, str):
"""
:type str: str
:rtype: bool
"""
import re
return bool(re.match(r"^([a-z]+)\1+$", str))
方案分析4
- 一不小心看到一个更牛的解决思路，笔者脑子是不够用，连简单的都想不到，不用说这位大神的想法了。下面给翻译大神的思路。
输入字符串的第一个字符串是重复子字符串的第一个字符
输入字符串的最后一个字符串是重复子字符串的最后一个字符
令S1 = S + S（其中输入字符串中的S）
删除S1的第一个和最后一个字符，生成字符串S2。
如果S存在于S2中，则返回true否则为false。
- 这个思想的精髓就在于通过拷贝一次字符串，并且各自破坏一小部分，然后通过两个串的拼接完成原串的查找。如果串不满足要求的特性，是拼装不出来的。
python实现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
