Java递归查找字符串中字符的最后一个索引

Question

这里是关于方法lastIndexOf的说明，ch是要匹配的字符，str是源字符串。

public static int lastIndexOf(char ch, String str) {
    // check for null string or empty string
    if (str.length() == 0 || str == null) {
        return -1;
    }

    int indexInRest = lastIndexOf(ch, str.substring(1));
    char first = str.charAt(0);

    // recursive call to find the last matching character
    if (first == ch) {
        return 1 + indexInRest; // this might not work properly
    } else
        return indexInRest;
}

如果在我的类的`main`方法中调用：

    System.out.println(lastIndexOf('r', "recurse"));
    System.out.println(lastIndexOf('p', "recurse"));

I got:

1
-1

期望的结果是：

4
-1

请提出建议。

- Hank

---

现有的方法 http://docs.oracle.com/javase/6/docs/api/java/lang/String.html#lastIndexOf%28int%29 有什么问题吗？ - Sean Patrick Floyd

是的，我需要建议。 - Hank

你正在从第一个字符到最后一个字符进行搜索，而不是从最后一个字符到第一个字符。此外，你的空值检查应该放在第一位，长度检查放在第二位。 - Gilbert Le Blanc

int lastIndexOf(int char) http://docs.oracle.com/javase/6/docs/api/java/lang/String.html#lastIndexOf%28int%29 接受一个 Unicode 字符值。由于这是递归作业，我肯定不能使用该方法。 - Hank

Answer 1

如何采用“功能性”方法..

public static int lastIndexOf(char ch, String str) {
    if (str.charAt(str.length() - 1) == ch) { return str.length() -1; }
    if (str.length() <= 1) { return -1; }
    return lastIndexOf(ch, str.substring(0, str.length() - 1));
}

- Johan Sjöberg

Answer 2

这一定是作业，因为API中已经存在String.lastIndexOf()方法，使用递归来实现这个功能会很慢并且占用大量内存。

这里有一个提示。目前你的算法是从前面切掉字符（substring(1)）并进行比较。lastIndexOf()应该从字符串的末尾开始移除字符并查找匹配项，然后在找到匹配项时停止。

- chubbsondubs

Answer 3

使用String#lastIndexOf(int ch)的实现作为一般指南，

public int lastIndexOf(int ch) {
    return lastIndexOf(ch, value.length - 1);
}

public int lastIndexOf(int ch, int fromIndex) {
    if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
        // handle most cases here (ch is a BMP code point or a
        // negative value (invalid code point))
        final char[] value = this.value;
        int i = Math.min(fromIndex, value.length - 1);
        for (; i >= 0; i--) {
            if (value[i] == ch) {
                return i;
            }
        }
        return -1;
    } else {
        return lastIndexOfSupplementary(ch, fromIndex);
    }
}

private int lastIndexOfSupplementary(int ch, int fromIndex) {
    if (Character.isValidCodePoint(ch)) {
        final char[] value = this.value;
        char hi = Character.highSurrogate(ch);
        char lo = Character.lowSurrogate(ch);
        int i = Math.min(fromIndex, value.length - 2);
        for (; i >= 0; i--) {
            if (value[i] == hi && value[i + 1] == lo) {
                return i;
            }
        }
    }
    return -1;
}

还有这个，

lastIndexOf(ch, value.length - 1);

value 是目标字符串作为字符数组。

- user1329572

---

需要注意的是Java使用迭代方法...您需要将其转换为递归方法。 - user1329572

Answer 4

首先，您应该更改为：

if (str == null || str.length() == 0) {

由于如果str为null，可能会引发NPE异常

请像这样在您的代码中添加一个deep参数：

public static int lastIndexOf(char ch, String str, int deep) {

并在每次递归调用中增加其值

int indexInRest = lastIndexOf(ch, str.substring(1), deep++);

然后，在返回语句中，将“deep”添加到您的返回值中：

return 1 + indexInRest + deep; // this might not work properly

第一次调用函数时使用 deep = 0，或者更好的方法是，使两个参数的方法 lastIndexOf 调用带有 deep 参数设置为 0 的 3 个参数版本的 lastIndexOf

- higuaro

Answer 5

你也可以使用Matcher来预测作业中要求的字符串分析的演变：

public int getlastMatch(String searchPattern,String textString) {
       int index = -1;
       Pattern pattern = Pattern.compile(searchPattern);
       Matcher matcher = pattern.matcher(textString);

       while(matcher.find()) {
               index = matcher.start();
       }
       return index;
   }

其中textString可能是你所关心的字符。

因此返回字符串中某个部分的最后出现。

- Mik378

Answer 6

为什么不像这样使用String.lastIndexOf：

str.lastIndexOf(ch)

- turtledove

---

很可能是因为这是一份作业，老师要求重新发明这个轮子。 - Don Roby