459. Repeated Substring Pattern

找到和第一个字符相同的字符，开始比对是否重复，如果重复，那么把字符串中相同的全部替换为空，如果结果为空，那么的确是符合要求的

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;
    }
}