家居网站建设基本流程,wordpress怎么添加字体,中文网站什么意思,江门市住房城乡建设局网站题意#xff1a;
给定一个非空的字符串 s #xff0c;检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s “abab” 输出: true 解释: 可由子串 “ab” 重复两次构成。
示例 2:
输入: s “aba” 输出: false
示例 3:
输入: s “abcabcabcabc” 输出: t…题意
给定一个非空的字符串 s 检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s “abab” 输出: true 解释: 可由子串 “ab” 重复两次构成。
示例 2:
输入: s “aba” 输出: false
示例 3:
输入: s “abcabcabcabc” 输出: true 解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)
提示
1 s.length 10^4s 由小写英文字母组成
题目来源 https://leetcode.cn/problems/repeated-substring-pattern/description/
解题方法
方法一从前往后主键加一截取长度作为子串重复拼接该子串是否与原字符串相等
// 从前往后主键加一截取长度作为子串重复拼接该子串是否与原字符串相等
function repeatedSubstringPattern($s) {$len strlen($s);if($len 1){return false;}for($i 1; $i $len; $i){// 从长度为1到s的长度减1作为子字符串$child_string substr($s, 0, $i); // 重复子字符串这里多重复一次是为了处理原长度为奇数时的情况$repeat_string str_repeat($child_string, intval(($len / $i) 1)); // 截掉多重复的一次子字符串 $repeat_string_s substr($repeat_string, 0, strlen($repeat_string) - $i);if($repeat_string_s $s){return true;}}return false;
}方法二字符串匹配参考KMP算法
// 字符串匹配参考KMP算法
function repeatedSubstringPattern($s) {return strpos(substr($s . $s, 1, -1), $s) ! false;
}方法三KMP算法找出最大重复前缀后缀
// KMP算法找出最大重复前缀后缀
function repeatedSubstringPattern($s) {$j 0;$next[0] 0;$len strlen($s);for($i 1; $i $len; $i){while($j 0 $s[$i] ! $s[$j]){$j $next[$j - 1];}if($s[$i] $s[$j]){$j;}$next[$i] $j;}if($next[$len - 1] 0 $len % ($len - $next[$len - 1]) 0){return true;}return false;
} 方法二、三参考 作者代码随想录 链接 https://leetcode.cn/problems/repeated-substring-pattern/solutions/1705527/by-carlsun-2-g3iz/ 来源力扣LeetCode
