JAVA 30+ lines and faster! Optimize first ranking answer by add a little but make it from 1088ms to 12ms


  • 0
    W

    When i check some fast answer, they are so many codes.

    the brute force code is little and easy to understand, i found some clues to avoid duplicate calculate.

    you will check the if(count2!=precount2){} clauses is the code i add, the thought is when s1 is at the ending and j==prej means "after that,all the for-loop is the duplicate calculations."

    so i use a direct while loop without char checking.

    public class Solution {
       public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
            if(n1==0) return 0;
            char[] array1 = s1.toCharArray(), array2 = s2.toCharArray();
            long count1 = 0, count2 = 0,precount2=0,precount1=0;
            int i = 0, j = 0,prej=0;
           
            while (count1 < n1) {
                if (array1[i] == array2[j]) {
                    j++;
                    if (j == array2.length) {
                        j = 0;
                        count2++;
                    }
                }
                i++;
                if (i == array1.length) {
                    i = 0;
                    count1++;
                    if(count2!=precount2){
                        if(precount2==0){
                            prej = j;
                            precount2 = count2;
                            precount1 = count1;
                        }
                        else if(j==prej){
                            long diff2 = count2-precount2,diff1 = count1-precount1;
                            while(count1<n1){
                                count1+=diff1;
                                count2+=diff2;
                            }
                            break;
                        } 
                    }
                }
            }
            return (int) (count2*n1/count1/ n2);
        }
    }
    

Log in to reply
 

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