*Java* 2 solutions: KMP O(m+n) & brute force O(mn)


  • 0
    E

    #Brute Force#

    public int strStr(String str, String pattern) {
    	int lenH = str.length(), len = pattern.length();
    	for(int i=0; i<=lenH-len; i++) {
    		if(pattern.equals(str.substring(i,i+len))) return i;
    	}
    	return -1;
    }
    

    #KMP (based on my understanding of this video)#

    public int strStr(String str, String pattern) {
    	char[] strs = str.toCharArray();
    	char[] patterns = pattern.toCharArray();
    	int L=strs.length, N=patterns.length, i=0, j=0; // i: str pointer, j: pattern pointer
    	if(N<1) return 0;
    	if(L<N) return -1;
    	int[] lps = lps(pattern); // get the array that stores the longest subarray whose prefix is also its suffix
    	while(i<L) {
    		if(strs[i]==patterns[j]) { // same value found, move both str and pattern pointers to their right
    		    ++i; 
    		    ++j;
    		    if(j==N) return i-N; // whole match found
    		}
    		else if(j>0) j = lps[j-1]; // move pattern pointer to a previous safe location
    		else ++i; // restart searching at next str pointer
    	}
    	return -1;
    }
    
    private int[] lps(String pattern) {
    	int j=0, i=1, L=pattern.length();
    	int[] res = new int[L];
    	char[] chars = pattern.toCharArray();
    	while(i<L) {
    		if(chars[i]==chars[j]) res[i++] = ++j;
    		else {
    			int temp = i-1;
    			while(temp>0) {
    				int prevLPS = res[temp];
    				if(chars[i]==chars[prevLPS]) {
    					res[i++] = prevLPS+1;
    					j = prevLPS;
    					break;
    				}
    				else temp = prevLPS-1;
    			}
    			if(temp<=0) {
    				res[i++] = 0;
    				j = 0;
    			}
    		}
    	}
    	return res;
    }
    

    Just for fun, here is a recursive one but has StackOverflowError:

    public int strStr(String str, String pattern) {
    	return strStr(str, str.length(), 0, pattern, pattern.length(), 0);
    }
    private int strStr(String str, int L, int i, String pattern, int N, int j) {
        if(j==N) return i-N;
        if(i>=L) return -1;
        if(str.charAt(i)!=pattern.charAt(j)) ++j;
        else j = 0;
        return strStr(str, L, ++i, pattern, N, j);
    }
    

Log in to reply
 

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