Leetcode 459. Repeated Substring Pattern

文章作者：Tyan
博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

解析：Version 1，字符串是子串的重复，则字符串的结尾字符为子串的结尾字符，且至少存在两个重复的子串，因此寻找子串时，阈值应为n // 2，找到与结尾字符相等的字符，设开始到结尾字符的子串为候选子串，遍历s，其如果满足条件，返回True，如果始终没找到，返回False。Version 2进行了进一步优化，利用了重复子串的性质，即拆下第一部分放到末尾仍等于字符串s。

Version 1

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        end = s[-1]
        for i in range(n // 2):
            if s[i] == end:
                pattern = s[:i+1]
                flag = True
                for i in range(0, len(s), len(pattern)):
                    if s[i:i+len(pattern)] != pattern:
                        flag = False
                        break
                if flag:
                    return True
        return False

Version 2

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        end = s[-1]
        for i in range(n // 2):
            if s[i] == end and s == s[i+1:] + s[:i+1]:
                return True
        return False

Reference

https://leetcode.com/problems/repeated-substring-pattern/