Java 26ms (no KMP)


  • 0
        /**
         * 100 / 100 test cases passed.
         * Status: Accepted
         * Runtime: 26 - 30 ms
         *
         * @param str
         * @return
         */
        public boolean repeatedSubstringPattern(String str) {
            boolean res = false;
            int len = 1, pre = 0; //pre is the repeated subString index
            for (int i = 1; i < str.length(); i++) {
                if (str.charAt(i) == str.charAt(pre)) {
                    pre++;
                    if (pre == len) {
                        pre = 0;
                        res = true;
                    }
                } else {
                    res = false;
                    //if fail, then the repeat len is become the current position
                    //because the situation of ababbaaaaa-ababbaaaaa, when pre is 1, and i is 10(the first char of second repeat index is 10)
                    //this time we need fallback! here has five a, we need back five times.
                    len = i - pre + 1;
                    if (len > str.length() / 2) break;
                    pre = 0;
                    i = len - 1;
                }
            }
    
            return res;
        }
    

    Can some one tell me the time complexity of my solution ?


Log in to reply
 

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