My Java Solution using KMP


  • 0
    L
    public class Solution {
        public int strStr(String haystack, String needle) {
            int i = 0;
            int j = 0;
            int next[] = new int[needle.length()];
            if(haystack.length() == 0 && 0 == needle.length())
                return 0;
            if(needle.length() == 0)
            	return 0;
            if(0 == needle.length())
            	return - 1;
            getNext(needle, next);
    
            while(i < haystack.length() && j < needle.length()){
            	if(j == -1 || haystack.charAt(i) == needle.charAt(j)){
            		i++;
            		j++;
            	}
            	else{
            		j = next[j];
            	}
            }
            if(j == needle.length())
            	return i - needle.length();
            return  -1;
        }
            
        public void getNext(String pattern, int next[]){
        	int k = -1;
        	int j = 0;
        	next[0] = -1;
        	
        	while(j < pattern.length() - 1){
        		if(-1 == k || pattern.charAt(j) == pattern.charAt(k)){
        			k++;
        			j++;
        			if(pattern.charAt(j) == pattern.charAt(k)){
        				next[j] = next[k];
        			}
        			else{
        				next[j] = k;
        			}
        		}
        		else{
        			k = next[k];
        		}
        	}
        }
    }

Log in to reply
 

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