patternjavaMajor
Custom indexOf() without String methods
Viewed 0 times
indexofwithoutmethodscustomstring
Problem
I created my own
Also, I want to ensure the program runs safely and correctly, the only test case I can think of it the length comparison.
indexOf function. I was wondering if anyone could help me come up with a way to make it more efficient. I am practicing for interviews so the catch is that I cannot use any String methods. I believe the runtime of this method is O(n2) with space of O(n). Correct me if I am wrong.Also, I want to ensure the program runs safely and correctly, the only test case I can think of it the length comparison.
public static int myIndexOf(char[] str, char[] substr) {
int len = str.length;
int sublen = substr.length;
int count = 0;
if (sublen > len) {
return -1;
}
for (int i = 0; i < len - sublen + 1; i++) {
for (int j = 0; j < sublen; j++) {
if (str[j+i] == substr[j]) {
count++;
if (count == sublen) {
return i;
}
} else {
count = 0;
break;
}
}
}
return -1;
}Solution
Complexity
Pedantically, the time-complexity is \$ O( m \times n ) \$, where
The Space complexity is \$ O(1) \$. You do not allocate any size-based memory structures.
Safety
It all looks good. There are no threading issues, no leaks, no problems.
Correctly
Nope, I don't like the lack of neat handling for invalid inputs.... you should be null-checking, etc. Getting a raw 'NullPointerException' looks bad.
Edit: Note that Josay has pointed out that your code (and my code below) produce different behaviour to
Alternative
I think your code is fine, but... I tend to use loop break/continue more than most... and, this saves a bunch of code in this case...
Also, for readability, I often introduce a
Consider the following loops which do not need the
Pedantically, the time-complexity is \$ O( m \times n ) \$, where
m is str.length and n is substr.length. This matters when \$ \left| m-n \right| \$ is large.The Space complexity is \$ O(1) \$. You do not allocate any size-based memory structures.
Safety
It all looks good. There are no threading issues, no leaks, no problems.
Correctly
Nope, I don't like the lack of neat handling for invalid inputs.... you should be null-checking, etc. Getting a raw 'NullPointerException' looks bad.
Edit: Note that Josay has pointed out that your code (and my code below) produce different behaviour to
String.indexOf() when the search term is the empty-string/empty-array.Alternative
I think your code is fine, but... I tend to use loop break/continue more than most... and, this saves a bunch of code in this case...
Also, for readability, I often introduce a
limit variable when the loop-terminator can be complicated....Consider the following loops which do not need the
count variable:int limit = len - sublen + 1;
searchloop: for (int i = 0; i < limit; i++) {
for (int j = 0; j < sublen; j++) {
if (str[j+i] != substr[j]) {
continue searchloop;
}
}
return i;
}
return -1;Code Snippets
int limit = len - sublen + 1;
searchloop: for (int i = 0; i < limit; i++) {
for (int j = 0; j < sublen; j++) {
if (str[j+i] != substr[j]) {
continue searchloop;
}
}
return i;
}
return -1;Context
StackExchange Code Review Q#44100, answer score: 31
Revisions (0)
No revisions yet.