链接
https://leetcode-cn.com/problems/repeated-substring-pattern/
耗时
解题:27 min
题解:4 min
题意
给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。
思路
尝试所有可能的 子串长度,1~n/2,如果某个长度能被 n 整除的话,说明有机会,尝试是否可以由这个长度的子串重复多次构成,如果可以直接返回 true,不行就尝试下一个子串长度。
时间复杂度:
O
(
n
2
)
O(n^2)
O(n2)
AC代码
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
for(int i = 1; i <= n/2; ++i) {
if(n%i == 0) {
string tmp = s.substr(0, i);
bool flag = true;
for(int j = i; j < n; j += i) {
if(tmp != s.substr(j, i)) {
flag = false;
break;
}
}
if(flag) {
return true;
}
}
}
return false;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)