java - 使用递归获取第一个字符串中第二个字符串第一次出现的索引

Question

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);                  
}    

我编写了这个方法来获取第一个字符串中第二个字符串的索引 但它有一个错误，它无法有效地返回第二个字符串的第一次出现，这是因为我正在使用逻辑从向后查找第二个字符串，并且我想不出任何其他逻辑。如有任何建议，我们将不胜感激。

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

Answer 1

正如您所指出的，您正在倒退。相反，你应该继续:

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;
        }
    }
}

示例:

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

它会像这样运行:

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