CODEWITHSUNDEEP
javaindexof
ShadowSeal
ShadowSeal

Reputation: 57

Writing custom indexOf() method in java

I'm currently trying to debug the indexOf() method I'm writing for a class called MyString. Here are the relevant methods:

public int indexOf(int startIndex, char ch) 
{
    if(startIndex < 0 || startIndex >= length())
    {
        System.out.println("\nFATAL ERROR: indexOf() given invalid startIndex\n");
        System.exit(0);
    }
    for(int i = startIndex; i < this.length(); i++)
    {
        if(this.charAt(i) == ch)
        {
            return i;
        }
    }
    return NOT_FOUND;
}


public int indexOf(MyString key)
{   
    if(key.length() > this.length())
    {
        return NOT_FOUND;
    }
    int indexOfFirstKeyLetter = indexOf(0, key.letters[0]);
    while(indexOfFirstKeyLetter != NOT_FOUND)
    {
        if(keyFound(indexOfFirstKeyLetter, key))
        {
            return indexOfFirstKeyLetter;
        }
        else
        {
            indexOfFirstKeyLetter = indexOf(indexOfFirstKeyLetter + 1, key.letters[0]);
        }
    }
    return NOT_FOUND;
}


private boolean keyFound(int indexOfFirstKeyLetter, MyString key) //Note: this method works for most strings, but doesn't work if the end of MyString is identical to the first few letters of key (ex: ado and dog falsely returns as true)
{
    for(int i = indexOfFirstKeyLetter; i < key.length() + indexOfFirstKeyLetter && i < this.length(); i++)
    {
        if(this.letters[i] != key.letters[i - indexOfFirstKeyLetter])
        {
            return false;
        }
    }
    return true;
}

I believe the issue lies in my keyFound method, where although it works for most strings, it will return true when the end of the the MyString Object being tested is identical to the first few letters of the key it's being compared to. For example, when testing "ado" and "dog" in the indexOf(MyString other) method, it returns a value of 1, indicating that the index of the beginning of the match is found at the location this.letters[1], when it should be returning NOT_FOUND, or -1, because the full key string "dog" is not located within "ado". Is there some way I can change my keyFound method to fix this issue?

Upvotes: 1

Views: 819

Answers (1)

R10t--
R10t--

Reputation: 829

What is happening is you're getting to the end of the string and exiting before it can check the whole comparison string:

Your logic is: is "dog" in "ado"? Find first index in 'ado' matching 'd', it's 1. "d" == "d". Nice, next letter, "o" == "o". Nice next letter. Wait. the 'ado' string is done. It must have been found. Return true.

You need an early exit condition in your keyFound function that returns false if it his the end of the string before it has searched the whole "key"'s length.

Just as a note, this is waaaaay more complicated than it has to be. You can easily do this with one loop. You're at O(n^3) right now with all the loops you have.

Upvotes: 1

Related Questions