Why my solution based on KMP exceeds time limit?


  • 0
    Y

    Time limit exceeded
    Last executed input:
    "aaaaaaaaaaaaaaaaa.......
    ......aaaaaaaaaaaab"

    I don't know where my code should be improved.
    Thanks in advance!

    public int strStr(String haystack, String needle) {
        		
        		int result = -1, i = 0, j = 0;
        		
        		if (haystack==null || needle==null || needle.length()>haystack.length()) 
        			return result;
        		
        		if (needle.length()==0) return 0;
        		
        		while (i<haystack.length() && j<needle.length()) {
        			if (haystack.charAt(i)==needle.charAt(j)) {
        				i++; //i is the index of character in the haystack
        				j++; //j is the max match length of the needle with the haystack
        				if (j==needle.length()) {
        					//Find the first occurrence of the needle as it may match the haystack several times
        					result = (result>0)?Math.min(result, i-j+1):(i-j+1);
        				}
        			}
        			else {
        				if (j!=0) {
        					/*If the needle matches the haystack till the jth character, but does not at the (j+1)th one
        					 *We need to calculate i where the next match work starts
        					 *So we calculate "step" besed on KMP "partial match table"
        					 */
        					i -= step(needle, j); //New match starts from the ith character of the haystack
        					j = 0; //Reset j, so that new match starts from the first character of the needle
        				}
        				else {
        					i++;
        				}
        			}
        		}
        		
        		return result;
        		
        	}
        	
        	//Below is the function of finding "step" base on KMP "partial match table".
        	public int step(String needle, int length) {
        		
        		int result = 0;
        		String s1 = "", s2 = "";
        		
        		for (int k=0; k<length; k++) {
        			s1 = s1 + needle.charAt(k); //s1 combines characters from the left of the needle to the right
        			s2 = needle.charAt(length-k-1) + s2; // s2 combines characters from the right to the left
        			if (s1.equals(s2) && s1.length()!=length) {
        				result = Math.max(s1.length(), result); //If s1 equals s2, we take down their length
        			}
        		}
        		
        		return result;
        		
        	}

  • 1
    N

    Man, you don't really understand KMP algorithm do you??
    KMP uses a table to record the number of steps that can be skipped for the scanner pointer. It processes the needle and generates the table once for all. That's basically the source of its swiftness.
    However, your implementation calls the "step" function every time the match fails, it causes O(N^2).


Log in to reply
 

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