459.Repeated Substring Pattern
459.Repeated Substring Pattern
难度: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.
1
Example 1:
2
3
Input: "abab"
4
Output: True
5
Explanation: It's the substring "ab" twice.
6
Example 2:
7
8
Input: "aba"
9
Output: False
10
Example 3:
11
12
Input: "abcabcabcabc"
13
Output: True
14
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)
Copied!
找出是否是循环字串,可以先统计26个字母出现的频次,然后找到所有出现次数不为0的最小公约数(至少为2),即最少的循环次数。然后比较。
1
lass Solution {
2
int max_factor(int a, int b)
3
{
4
if(a<b) swap(a,b);
5
if(b==0) return a;
6
for(int i=2;i<=b;i++)
7
if(a%i==0 && b%i ==0 )return i;
8
return 1;
9
}
10
public:
11
bool repeatedSubstringPattern(string s) {
12
vector<int>alpha(26,0);
13
for(auto c:s)
14
++alpha[c-'a'];
15
int len=0;
16
for(auto i:alpha)
17
// {
18
len=max_factor(len,i);
19
// cout<< i<<" ";
20
// }
21
// cout<<endl;
22
// cout<< len << " "<<endl;
23
24
if(len == 1 )return false;
25
26
int one_size=s.length()/len;
27
// cout<<one_size<<endl;
28
for(int j=0;j<one_size;j++)
29
for(int i=1;i<len;i++)
30
if(s[i*one_size+j] !=s[j]) return false;
31
return true;
32
33
}
34
};
Copied!
执行用时 :28 ms, 在所有 C++ 提交中击败了97.08%的用户 内存消耗 :11.5 MB, 在所有 C++ 提交中击败了94.35%的用户
Copy link