-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path459.cpp
More file actions
34 lines (28 loc) · 1019 Bytes
/
Copy path459.cpp
File metadata and controls
34 lines (28 loc) · 1019 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
459. 重复的子字符串
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
来源：力扣（LeetCode）
链接： https://leetcode.cn/problems/repeated-substring-pattern/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
class Solution {
public:
bool repeatedSubstringPattern(string s) {
if (s.empty()) return false;
int n = s.size();
// 枚举长度为l的子串，l的最大长度不会超过n/2
for (int l = 1; l <= n / 2; l++) {
if (n % l) continue; // 如果长度l不能构成长度为n的串
bool matched = true;
for (int j = l; j < n; j++) {
if (s[j - l] != s[j]) { // 有一个不匹配，跳过
matched = false;
break;
}
}
// 是否匹配
if (matched) return true;
}
return false;
}
};