deepak rao deepak rao - 1 month ago 6
Java Question

Get index of first occurrance of second string in the first String using recursion

public int indexOf(String s1,String s2){
if(s1.length()<s2.length())
return -1;
else if(s1.substring(s1.length()-s2.length()).equals(s2))
return s1.length()-s2.length();
else
return indexOf(s1.substring(0,s1.length()-1),s2);
}


I wrote this method to get index of the second string in the first one
but it has a bug it cant effectively return first occurrence of the second string this is because I am using logic to find the second string from backwards and I could not think of any other logic. Any suggestions would be appreciated.

example of a failure case: firstString "BarackObama" second string "a"

Answer

As you noted, you are doing it backwards. Instead, you should go forward:

public static int indexOf(String s1, String s2){
    if(s1.length()<s2.length()) {
        return -1;
    }
    else if(s1.substring(0, s2.length()).equals(s2)) {
        return 0;
    }
    else {
        int i = indexOf(s1.substring(1, s1.length()), s2);
        if (i == -1) {
            return i;
        } else {
            return 1 + i;
        }
    }
}

Example:

String s1 = "BarackObama";
String s2 = "rac";
indexOf(s1, s2);

It would run like this:

indexOf("BarackObama", "rac"):
    "BarackObama".substring(0, 3).equals("rac") -> false
    return 1 + indexOf("BarackObama".substring(1, 11), "rac")

indexOf("arackObama", "rac"):
    "arackObama".substring(0, 3).equals("rac") -> false
    return 1 + indexOf("arackObama".substring(1, 10), "rac")

indexOf("rackObama", "rac"):
    "rackObama".substring(0, 3).equals("rac") -> true
    return 0;

return 0 + 1 + 1 = 2