No KMP,Java O((n/2)^2) complexity solution,easy to understand


  • 1
    D
    public boolean repeatedSubstringPattern(String s) {
        if (s == null || s.length() < 1) {
    	return false;
        }
       char[] chs = s.toCharArray();
    	for (int i = chs.length / 2; i >= 1; i--) {
    		if (chs.length % i == 0) {
    			int divided = chs.length / i;
    			boolean flag = true;
    			for (int index = 0; index < i; index++) {
    				for (int j = 1, t = divided - 1; j <= t; j++, t--) {
    					if (chs[index] != chs[index + j * i] || chs[index] != chs[index + t * i]) {
    						flag = false;
    						break;
    					}
    				}
    				if (index == i - 1 && flag) {
    					return true;
    				}
    			}
    		}
    	}
           return false;
    	}
    

    Explaination:
    For instance,string "abcabcabc",firstly,we should find out each probability of the string (Half of the string,obviously).
    when we got substring "abc",we should match each group after the substring,so,next step we should compare each position between substring and next group,
    if I define i as the begin on substring,
    we should compare i and i + each step length (substring length) are equal or not until the end of whole string.

    Time complexity about O( (n/2)^2) also O(n^2)


Log in to reply
 

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