Question: Implement strstr in Java. Find the first instance of a string in another string.
Answer:
public int Search(String haystack, String needle){
for(int i = 0; i < haystack.length(); i++ ) {
for(int j = 0; j < needle.length() &&
i+j < haystack.length(); j++ ) {
if(needle.charAt(j) != haystack.charAt(i+j)) {
break;
} else if (j == needle.length()-1) {
return i;
}
}
}
return -1;
}
Like this question? Follow our feed and tweet it.
Complexity is n square. Can we do it better than this?
This is the rather naive implementation, however accurate. You should take a look at the Knuth-Morris-Pratt (KPM) algorithm:
http://en.wikipedia.org/wiki/Knuth-morris-pratt
Didn’t know about indexOf.. but this would make it too simple.
Here is what I did.
/**
* Returns the position where the substring toFind in s starts. -1 if it's not found.
* @param s
* @param toFind
* @return
*/
static int strStr(String s, String toFind) {
int pos = -1;
int i = 0, j = 0;
for(; i<s.length(); i++) {
if(j == toFind.length()) {
return pos;
}
if (pos == -1 && s.charAt(i) == toFind.charAt(0)) {
pos = i;
j = 1;
continue;
} else if (s.charAt(i) == toFind.charAt(j)) {
j++;
} else {
j = 0;
pos = -1;
}
}
return pos;
}
Isn’t this simply a String.indexOf(String str)? Which strstr do you mean, the C, PHP, …?