青岛做网站推广公司哪家好,网站做电商资质,友点网站建设,莱芜有需要制作网站的公司吗第四章 字符串part02 28. 实现strStr() 459. 重复的子字符串
一、28. 实现strStr() 题目链接#xff1a;https://leetcode.cn/problems/repeated-substring-pattern/ 题目介绍#xff1a; 给定一个非空的字符串 s #xff0c;检查是否可以通过由它的一个子串重复多次构成。…第四章 字符串part02 28. 实现strStr() 459. 重复的子字符串
一、28. 实现strStr() 题目链接https://leetcode.cn/problems/repeated-substring-pattern/ 题目介绍 给定一个非空的字符串 s 检查是否可以通过由它的一个子串重复多次构成。 示例 1: 输入: s abab
输出: true
解释: 可由子串 ab 重复两次构成。代码
class Solution {public boolean repeatedSubstringPattern(String s) {if (s.equals()) return false;int len s.length();// 原串加个空格(哨兵)使下标从1开始这样j从0开始也不用初始化了s s;char[] chars s.toCharArray();int[] next new int[len 1];// 构造 next 数组过程j从0开始(空格)i从2开始for (int i 2, j 0; i len; i) {// 匹配不成功j回到前一位置 next 数组所对应的值while (j 0 chars[i] ! chars[j 1]) j next[j];// 匹配成功j往后移if (chars[i] chars[j 1]) j;// 更新 next 数组的值next[i] j;}// 最后判断是否是重复的子字符串这里 next[len] 即代表next数组末尾的值if (next[len] 0 len % (len - next[len]) 0) {return true;}return false;}
}二、459. 重复的子字符串 题目链接https://leetcode.cn/problems/repeated-substring-pattern/ 题目介绍 给定一个非空的字符串 s 检查是否可以通过由它的一个子串重复多次构成。 示例 1: 输入: s abab
输出: true
解释: 可由子串 ab 重复两次构成。代码
class Solution {public boolean repeatedSubstringPattern(String s) {if (s.equals()) return false;int len s.length();// 原串加个空格(哨兵)使下标从1开始这样j从0开始也不用初始化了s s;char[] chars s.toCharArray();int[] next new int[len 1];// 构造 next 数组过程j从0开始(空格)i从2开始for (int i 2, j 0; i len; i) {// 匹配不成功j回到前一位置 next 数组所对应的值while (j 0 chars[i] ! chars[j 1]) j next[j];// 匹配成功j往后移if (chars[i] chars[j 1]) j;// 更新 next 数组的值next[i] j;}// 最后判断是否是重复的子字符串这里 next[len] 即代表next数组末尾的值if (next[len] 0 len % (len - next[len]) 0) {return true;}return false;}
}
