6ms Java Solution with pure char matching


  • 0
    F

    The solution has two steps: 1) find a start position in A where the suffix of A from that position is a prefix in B; 2) based on step 1, find if multiple As contain B.

    The high performance lays in the char matching in step 2. It doesn't rely on StringBuilder or any built-in String matching methods by purely looping A while iterating B, which speeds up the matching process.

    The codes are a bit messy but hope the idea helps!

    class Solution {
        public int repeatedStringMatch(String A, String B) {
            if(A == null || B == null) return -1;
            int rep = 1, lenA = A.length(), lenB = B.length();
            int j = 0;
            
            // find if a start point exists in A
            for(int i = 0; i < lenA; i++) {
                if(A.charAt(i) == B.charAt(0)) {
                    int s = i;
                    while(s < lenA && s - i < lenB && A.charAt(s) == B.charAt(s - i)) s++;
                    if(s - i == lenB) return 1;
                    else if(s == lenA) {
                        rep++;
                        j = s - i;
                        break;
                    }       
                }
            }
            if(j == 0) return -1;
                   
            // find out if B can be a substring with multiple As
            for(int i = 0; j < lenB; j++,i++){
                if(i == lenA) {
                    i = 0;
                    rep++;
                }
                if(B.charAt(j) != A.charAt(i)) return -1;
            }
                   
            return rep;    
        }
    }
    

Log in to reply
 

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