LeetCode Q28: Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

This question is suppose to be very easy, however, I confuse this question with LeetCode Q3: Longest substring without repeating characters. Thus made many mistakes in the first several tries.

Basically, the simplest solution is brute force one which is similar to code below:

	class Solution {
	public:
	int strStr(string haystack, string needle) {
	int len0=haystack.length();
	int len1=needle.length();
	if(len1==0)
	return 0;
	for(int i=0; i<len0-len1+1; ++i){
	if(haystack[i]!=needle[0])
	continue;
	int j=0;
	for(j=0; j<len1; ++j){
	if(haystack[i+j]!=needle[j])
	break;
	}
	if(j==len1)
	return i;
	}
	return -1;
	}
	};

view raw Q28strStr.cpp hosted with ❤ by GitHub

Yet, the optimal solution is KMP algorithm which I don't think most people can understand and are expected to finish during interview, so skip.



Rount 2.
Use Boyer-Moore algorithm which is easier to understand than KMP and 3-5 times faster than KMP.

	class Solution {
	public:
	int strStr(string haystack, string needle) {
	int jump[256]; // hashmap char-> index, assume ASCII
	int nlen=needle.length();
	int hlen=haystack.length();
	for(int i=0; i<256; i++)
	jump[i]=-1;
	for(int i=0; i<needle.length(); i++)
	jump[needle[i]] = i; // index of last occurrence
	int skip=0;
	for(int i=0; i<hlen-nlen+1; i+=skip) { // !!! not i<hlen
	skip=0;
	for(int j=nlen-1; j>=0; j--) {
	if(haystack[i+j]!=needle[j]) {
	skip =max( 1, j-jump[haystack[i+j]] ); // max is j+1, min is 1 (do not allow <0);
	break;
	}
	}
	if(skip==0) return i;
	}
	return -1;
	}
	};

view raw Q28.cpp hosted with ❤ by GitHub