给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
输入: "aba"
输出: False
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
class Solution {
/**
* @param String $s
* @return Boolean
*/
function repeatedSubstringPattern($s) {
/** 暴力解法 **/
if (strlen($s) === 1) { // 没有子串
return false;
}
$length = strlen($s);
for ($i = 1; $i < ($length / 2 + 1); $i++) { // 控制截取长度
// 如果s长度为i的整数倍,再判断该长度的子串是否可以多次构成原字符串
if ($length % $i == 0) {
// 思路一:第一个子串与后面所有子串对比,不同则改变flag标志位
$flag = true;
$str = substr($s, 0, $i);
for ($j = $i; $j < $length; $j += $i) { // 控制开始位置
if ($str !== substr($s, $j, $i)) {
$flag = false;
}
}
if ($flag) return true;
// 思路二:把每一个子串截取塞进数组,最后去重判断数组元素数量是否等于1
// $arr = [];
// for ($j = 0; $j < $length; $j += $i) {
// $arr[] = substr($s, $j, $i);
// }
// if (count(array_unique($arr)) == 1) {
// return true;
// }
}
}
return false;
/** 别人家孩子的解法 **/
// 假设母串S是由子串s重复N次而成, 则 S+S则有子串s重复2N次, 现在S=Ns, S+S=2Ns 因此S在(S+S)[1:-1]中必出现一次以上
// return strpos(substr($s . $s, 1, -1), $s) !== false;
}
}
暂无相关文章!
技术流,拜读一下
可以
新冠肆虐,注意安全!
不知道说什么好,还是祝疫情早点结束吧!