java - 实现我自己的 indexOf 方法的递归版本

Question

所以我试图编写递归方法indexOf，它返回第一个字符串中第二个字符串第一次出现的起始索引(如果不是，则返回-1)例如，调用indexOf(“Barack Obama”,“bam”)将返回8。另外我知道String类有方法IndexOf，但我不想使用它.

到目前为止，这是我的代码:

public class MyClass {

    public static void main(String[] args) {
    }

    public static int indexOf(String s, String t) {
        return abc(s, t, 0);
    }

    public static int abc(String a, String b, int c) {
        if ((a.length() - c) < b.length()) {
            return -1;
        } else if (b.equals(a.substring(c, c + 3))) {
            return c;

        } else {

        }
    }
}

Answer 1

这取决于您想要使用多少库。

一个选项是:

int indexOf(String container, String text, int index) {
  //Too short container
  if (container.length() < text.length()) return -1; 
  //found
  else if (container.startsWith(text)) return index;
  //keep searching
  else return indexOf(container.substring(1), text, index+1);
}
indexOf("banana", "nana", 0) == 2;

如果您不想使用.startsWith，那么您需要实现自己的版本。一个非常好的练习是尝试在不使用 .substring 方法的情况下执行此操作，这很糟糕(因为它创建了字符串的副本，O(n) 空间/时间性能)，并且此任务不需要该方法(使用.charAt)

您还可以将官方方法indexOf从其包含索引的递归调用中分离出来，以便更加清晰)。

您也应该仔细考虑边缘情况:)