049--力扣刷题459--重复的子字符串-pin2字符串构造

2字符串构造

有一个长度为n的字符串P，我们可以通过P构造出一个无限长度的字符串S,其中S[i]=P[i%n]。给定一个字符串S，求可以通过上述方法构造出S的最短字符串P。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import sys
#s =sys.stdin.readline().strip()
s='abcdabcabc'
n=len(s)
for i in range(1,n//2):
    p=''.join(s[0:i])
    q=''
    for j in range(n):
        q=q+p[j%(len(p))]
    if q == s:
        print(p)
        break
    if i == (n//2)-1: #查找到了中间也不能满足的话说明只有原来的串才是可以的
        print(s)

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:

输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。 示例 2:

输入: "aba"

输出: False 示例 3:

输入: "abcabcabcabc"

输出: True

解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        for l in range(1,len(s)//2+1):
            if s[:l] * (len(s)//l) == s:
                return True
        return False

看了评论区python一行代码高赞解答，理解了一下，给大家参考。

  • 一个字符串如果符合要求，则该字符串至少由2个子串组成。例：b b / abc abc

s+s。以后，则该字符串至少由4个子串组成 bb+bb / abcabc+abcabc

  • 截去首尾各一个字符s[1:-1] （注：只截一个是为了判断类似本例，重复子串长度为1的情况。当重复子串长度大于1时，任意截去首尾小于等于重复子字符串长度都可）

  • 由于s+s组成的4个重复子串被破坏了首尾2个，则只剩下中间两个 b bb b。此时在判断中间两个子串组成是否等于s，若是，则成立。

1
2
3
class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return (s + s)[1: -1].find(s) != -1