java - 使用递归的indexOf方法

Question

我需要编写一个名为indexOf的递归方法，它接受两个字符串作为参数，并返回第一个字符串中第二个字符串第一次出现的起始索引(如果未找到，则返回-1)。我必须使用递归来解决这个问题。以下是一些示例结果:

indexOf("Barack Obama", "Bar")  0

indexOf("Barack Obama", "ck")  4

indexOf("Barack Obama", "a")  1

indexOf("Barack Obama", "McCain")  -1

indexOf("Barack Obama", "BAR")  -1

这是我的解决方案，但它给了我 6 的 indexOf("Barack Obama", "McCain")，而不是 -1。

public static int indexOf(String s1, String s2) {
        if(s1.equals(s2))
            return 0;

        else
            return indexOfHelper(s1, s2, 0); 
    }
private static int indexOfHelper(String s1, String s2, int ctr) {
        if(s2.length() > s1.length())
            return -1;

        if(s2.length() == 0 || s1.length() == 0)    //base case
            return ctr;     

        else                    //recursive case
            if(s1.charAt(0) == s2.charAt(0)){       //if there is a matching character
                if(s1.substring(0, s2.length()).equals(s2))
                    return ctr;     //if there is a matching character and the rest of the strings match as well
                else
                    return -1;        //if there is a matching character but the rest of the strings don't match
            }
            else
                return 1 + indexOfHelper(s1.substring(1), s2, ctr);

}

Answer 1

我必须说递归步骤非常棘手。它通过了所有测试用例。我希望以下有所帮助。 Java 和 C++ 代码在这里

JAVA

int indexOf (String s1, String s2) {

    if (s1.length() == 0 && s2.length() == 0) {
        return 0;
    } else if (s1.length() == 0) {
        return -1;
    } else if (s2.length() == 0) {
        return 0;
    } else if (s2.length()>s1.length()) {
        return -1;
    }
    else if (s1.charAt(0)  == s2.charAt(0)) {
        int subIndex = indexOf(s1.substring(1),s2.substring(1));
        return  subIndex == -1 ? -1: subIndex;


    } else {
        int subIndex = indexOf(s1.substring(1),s2);
        return  subIndex == -1 ? -1: subIndex+1;
    }

}

此处为 C++ 代码

int indexOf (string s1, string s2) {

        if (s1 == "" && s2 == "") {
            return 0;
        } else if (s1 == "") {
            return -1;
        } else if (s2=="") {
            return 0;
        } else if (s2.size()>s1.size()) {
            return -1;
        }
        else if (s1 [0] == s2[0]) {
            int subIndex = indexOf(s1.substr(1,s1.length()),s2.substr(1,s2.length()));
            return  subIndex == -1 ? -1: subIndex;


        } else {
            int subIndex = indexOf(s1.substr(1,s1.length()),s2);
            return  subIndex == -1 ? -1: subIndex+1;
        }

    }