java recursion find the last index of a character in a string

Question

Here is what I have for method lastIndexOf , ch is the character to match, and str is the source string.

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

If in my class' main method I call:

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

I got:

1
-1

The desired result is:

4
-1

Suggestion, please.

and what is wrong with the existing method docs.oracle.com/javase/6/docs/api/java/lang/… ? — Sean Patrick Floyd
– Sean Patrick Floyd, Commented Sep 27, 2012 at 15:05
You're searching from the first character to the last, instead of from the last character to the first. Also, your null check should be first and the length check second. — Gilbert Le Blanc
– Gilbert Le Blanc, Commented Sep 27, 2012 at 15:07
int lastIndexOf(int char) <docs.oracle.com/javase/6/docs/api/java/lang/…> takes an unicode value of character. As this is a homework for recursion. I definitely cannot use that method. — Hank
– Hank, Commented Sep 27, 2012 at 15:09

Johan Sjöberg · Accepted Answer · 2012-09-27 15:15:17Z

3

How about taking the functional approach..

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

edited Sep 27, 2012 at 15:15

answered Sep 27, 2012 at 15:09

Johan Sjöberg

49.4k22 gold badges135 silver badges150 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

chubbsondubs · Accepted Answer · 2012-09-27 15:08:24Z

3

This must be homework because there would be no point to writing this method since String.lastIndexOf() exists in the API, and using recursion to do this going to be slow and use a lot of memory.

Here a hint. Right now your algorithm is chopping characters off the front ( substring(1) ) and comparing them. lastIndexOf() should start by removing characters at the back of the String looking for a match then quit when it finds one.

answered Sep 27, 2012 at 15:08

chubbsondubs

39.4k25 gold badges110 silver badges143 bronze badges

Comments

Baz · Accepted Answer · 2012-09-27 15:07:10Z

0

why not use String.lastIndexOf like this:

str.lastIndexOf(ch)

edited Sep 27, 2012 at 15:07

Baz

37k11 gold badges75 silver badges101 bronze badges

answered Sep 27, 2012 at 15:06

turtledove

26k3 gold badges25 silver badges20 bronze badges

1 Comment

Don Roby Over a year ago

Likely because it's homework and the teacher has requested reinventing this wheel.

user1329572 · Accepted Answer · 2012-09-27 15:07:40Z

0

Use the String#lastIndexOf(int ch) implementation as a general guideline,

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

And this,

lastIndexOf(ch, value.length - 1);

value is the target String as a character array.

answered Sep 27, 2012 at 15:07

user1329572

6,4265 gold badges31 silver badges39 bronze badges

1 Comment

user1329572 Over a year ago

It's important to note that Java uses the iterative approach...you'll need to convert this to a recursive approach.

dinox0r · Accepted Answer · 2012-09-27 15:08:22Z

0

First, you should change to:

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

Because a NPE could raise if str is null

Add a deep paramater to your code like this:

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

And increment its value every recursive call

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

then, in the return sentence, add deep to your returned value:

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

Call the function the first time with deep = 0, or better yet, make the two parameter method lastIndexOf call the 3 parameters version of lastIndexOf with the deep parameter set to 0

answered Sep 27, 2012 at 15:08

dinox0r

16.1k4 gold badges39 silver badges43 bronze badges

Comments

Mik378 · Accepted Answer · 2012-09-27 15:09:07Z

0

You can also use Matcher in order to anticipate evolution of string analysis asked by your homework:

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

where textString may be your concerned character.

Thus returning the last occurence of a part of string within a string.

answered Sep 27, 2012 at 15:09

Mik378

22.2k15 gold badges95 silver badges191 bronze badges

Collectives™ on Stack Overflow

java recursion find the last index of a character in a string

6 Answers 6

Comments

Comments

1 Comment

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

Comments

1 Comment

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related