美文网首页
459. Repeated Substring Pattern

459. Repeated Substring Pattern

作者: hyhchaos | 来源:发表于2016-12-01 14:17 被阅读190次

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

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

    相关文章

      网友评论

          本文标题:459. Repeated Substring Pattern

          本文链接:https://www.haomeiwen.com/subject/hfmxmttx.html