找到和第一个字符相同的字符,开始比对是否重复,如果重复,那么把字符串中相同的全部替换为空,如果结果为空,那么的确是符合要求的
Java
public class Solution {
public boolean repeatedSubstringPattern(String str) {
for(int i=1;i<str.length();i++)
{
if(str.length()%i==0)
{
if(str.charAt(0)==str.charAt(i))
{
int j=0;
while(j<i&&(i+j)<str.length())
{
if(str.charAt(j)==str.charAt(i+j))
j++;
else
break;
}
if(j==i)
{
String res=str.replaceAll(str.substring(0,i),"");
if(res.equals(""))
return true;
}
}
}
}
return false;
}
}
Javascript
/**
* @param {string} str
* @return {boolean}
*/
var repeatedSubstringPattern = function(str) {
for(var i=1;i<str.length;i++)
{
if(str.length%i===0)
{
if(str[0]==str[i])
{
var j=0;
while(j<i&&(i+j)<str.length)
{
if(str[j]==str[i+j])
j++;
else
break;
}
if(j==i)
{
var res=str.replace(new RegExp(str.substring(0,i),"gm"),"");
if(res==="")
return true;
}
}
}
}
return false;
};
优解,Java
public boolean repeatedSubstringPattern(String str) {
int len = str.length();
for(int i=len/2 ; i>=1 ; i--) {
if(len%i == 0) {
int m = len/i;
String subS = str.substring(0,i);
int j;
for(j=1;j<m;j++) {
if(!subS.equals(str.substring(j*i,i+j*i))) break;
}
if(j==m)
return true;
}
}
return false;
}
最优解,KMP算法,还有一个Z算法
public class Solution {
public boolean repeatedSubstringPattern(String str) {
//This is the kmp issue
int[] prefix = kmp(str);
int len = prefix[str.length()-1];
int n = str.length();
return (len > 0 && n%(n-len) == 0);
}
private int[] kmp(String s){
int len = s.length();
int[] res = new int[len];
char[] ch = s.toCharArray();
int i = 0, j = 1;
res[0] = 0;
while(i < ch.length && j < ch.length){
if(ch[j] == ch[i]){
res[j] = i+1;
i++;
j++;
}else{
if(i == 0){
res[j] = 0;
j++;
}else{
i = res[i-1];
}
}
}
return res;
}
}
优解,正则
public class Solution {
public boolean repeatedSubstringPattern(String str) {
if(str == null || str.length() < 2) return false;
boolean result = false;
for(int i = 1; i <= str.length()/2; i++) {
if(str.length()%i != 0) continue;
String regex = "("+str.substring(0,i)+")" + "+";
result = result | str.matches(regex);
}
return result;
}
}
网友评论