Optimized Simple Java Solution with Prime Table(Fast)


  • 1
    J

    Firstly, let's look at the code.

    public class Solution {
        private boolean check(String str, int seg) {
            int L = str.length();
            if(L % seg != 0) {
                return false;
            }
    
            int segL = L / seg;
    
            String S = str.substring(0, segL);
            for(int i = 1; i < seg; i ++) {
                if(!S.equals(str.substring(segL * i, segL * i + segL))) {
                    return false;
                }
            }
    
            return true;
        }
    
        public boolean repeatedSubstringPattern(String str) {
            int L = str.length() + 1;
            boolean[] p = new boolean[L];
            for(int i = 2; i < L; i ++) {
                if(p[i]) continue;
    
                if(check(str, i)) {
                    return true;
                }
    
                for(int j = 2; j * i < L; j ++) {
                    p[i * j] = true;
                }
            }
    
            return false;
        }
    }
    

    The core algorithm is very simple, you try to cut the string into 2 segment, 3 segment, 4 segment, 5 segment, and test whether the prefix is the same as the following segments.

    However, there is something that we can further optimized. Say, we have already tested that cutting the array into 2 segment is does not work, is it still necessary for us to cutting the array into 4(or 8 or 16) segments? The answer is NO.

    Here is the proof.

    If cutting the array into 4 or 8 or 16 or ... segments works => Then cutting the array into 2 segment will definitely work!. (Very obvious, we can just merge segments and prove)

    Then according to logical rule

    If cutting the array into 2 segment does NOT work => cutting the array into 4 or 8 or 16 or ... segments does NOT work!

    To further expand the theory, we DO NOT want to test any non-prime segment.

    We use a prime table p to store whether a number is prime or not. The prime selection algorithm is here: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

    Then, for each prime number N, we cut the array into N segments and do the repeatation test.


  • 0

    @jinyao Good observation for an upvote! Can't believe such simple optimization is missed by many posts here... Prime divisors should be much sparse than all divisors. If the prime table is pre-calculated and method repeatedSubstringPattern is called millions of times, your method will show even more performance advantage.

    "We use a prime table p to store whether a number is prime or not"

    It seems that your p[i] = true means i is a non-prime number.


Log in to reply
 

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