HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMajor

Custom indexOf() without String methods

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
indexofwithoutmethodscustomstring

Problem

I created my own 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 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.