【LeetCode 459】关关的刷题日记42 – Repeated Substring Pattern- 专知

【LeetCode 459】关关的刷题日记42 – Repeated Substring Pattern

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记42 – Leetcode 459. Repeated Substring Pattern

题目

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

题目的意思是给定一个字符串，来判断它是否可以由一个子串重复若干次构成。

思路

思路：遍历给定字符串s的前半部分，来找可能重复若干次构成s的子串。那怎么找这个可能的子串呢？遍历过程中得到的字符s[i]和s[0]相等的时候，再进一步判断s.substr(0,i-1)这个字符串是否是目标子串，判断之前还可以进一步优化，看下s.substr(0,i-1)的长度是否能被s.size()整除，不能整除的话也不用判断了。

class Solution {public:    bool repeatedSubstringPattern(string s) {        if(s.empty()  || s.size()==1)            return false;        for(int i=1; i<=s.size()/2; ++i)        {            if(s[i]==s[0])            {                string temp=s.substr(0,i);                if(s.size()%i!=0)                    continue;                int flag=1;                for(int j=i; j<s.size(); j=j+i)                {                    if(s.substr(j,i)!=temp)                    {                        flag=0;                        break;                    }                    }                if(flag)                    return true;                else                {                    flag=1;                }            }                        }        return false;    }};