This solution is definitely NOT KMP, really intuitive


  • 0

    first get all the factor of the length of str. The possible substring length should be coming from those factors.

        public boolean repeatedSubstringPattern(String str) {
            if (str == null || str.length() <= 1) return false;
            int n = str.length();
            List<Integer> cuts = new ArrayList<>();
            cuts.add(1);
            for (int i = 2; i <= (int)Math.sqrt(n); i++) {
                if (n % i == 0) {
                    cuts.add(i);
                    if (i != n / i) cuts.add(n / i);
                }
            }
    
            // n = 12, cuts = {1,2,3,4,6}
            String temp = "";
            boolean res = true;
            for (int cut : cuts) {
                res = true;
                temp = str.substring(0, cut);
                for (int i = cut; i <= n - cut; i += cut) {
                    String test = str.substring(i, i + cut);
                    if (!test.equals(temp)) {
                        res = false;
                        break;
                    }
                }
                if (res) return true;
            }
            return false;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.