Using recursion to count substrings (with exceptions to the rule) in Java

Question

I am going through the CodingBat exercises for Java. Here is the one I have just finished:

Given a string, compute recursively the number of times lowercase hi appears in the string, however do not count hi that have an x immedately before them.

And here is my code:

public int countHi2(String str) {

    if (str.length() < 3) {
        return str.equals("hi") ? 1 : 0;
    }

    if (str.substring(0, 3).equals("xhi")) {
        return countHi2(str.substring(2));
    }

    if (str.substring(0, 2).equals("hi")) {
        return 1 + countHi2(str.substring(2));
    } else {
        return countHi2(str.substring(1));
    }

}

This is the first in a recursion exercise which I have needed to change the base case to accommodate how the rest of the code works. I originally made it so that whenever an x is reached, it returns a substring from 2 (because the following hi is irrelevant), but of course, this is useless when there are two x's adjacent to one another.

I am still getting used to the idea of recursion, so I would like to know if this is a 'good' solution or not. Can it be made more efficient?

Answer 1

Similar to @Ben Aaronson above but uses indexOf() instead of startsWith()

public int countHi2(String str) {
    int pos = str.indexOf("hi");
    if (pos == -1) {
       return 0;
    }
    int increment = (pos == 0 || str.charAt(pos-1) != 'x') 
                      ? 1
                      : 0;   
    return countHi2(str.substring(pos+2))
           + increment;
}

Answer 2

I don't have much negative to say about this- the algorithm seems good, and it's expressed in a way that's clear and easy to understand. The only points I might pick up on:

Naming/style

• str isn't a great name, though this is one of those situations you often run into with coding challenges where there isn't much more descriptive you can say about a value than its type. It could probably at least be lengthened to string. Alternatively, for methods doing this kind of analysis on a single input value, I sometimes like the name target- or maybe input.
• There's probably some significance to the 2 in countHi2, but it shouldn't really be there. If it's because you'd previously done an iterative version, countHiRecursive would be better.
• Arguably you could remove the final else. In this case I'd say it's somewhat a matter of taste, especially since you only have a single line with the extra indentation rather than a larger block.

Algorithm

The one thing that could make this a little clearer is changing the first conditional. To me it seems to be conflating two things- looking for "hi" (which happens in the final conditional too) and terminating the recursion when you run out of string.

Since the last conditional takes care of counting "hi", it might be slightly clearer to replace the first one with:

if (str.length() < 2) {
    return 0;
}

Using in-built methods

Beyond the above, you could potentially give more instant readability by using the in-built java String.startsWith.

That makes your code a bit more DRY because you're not specifying multiple times the exact implementation of how you calculate whether a string starts with a certain value. It also improves readability quite a bit.

All together

So with all the above changes, you get:

public int countHi(String target) {
    if (target.length() < 2) {
        return 0;
    }

    if (target.startsWith("xhi")) {
        return countHi(target.substring(2));
    }

    if (target.startsWith("hi")) {
        return 1 + countHi(target.substring(2));
    } else {
        return countHi(target.substring(1));
    }
}

Answer 3

return countHi2(str.substring(1));

This line can be changed to

int nextIndex = Math.min(Math.max(1, str.indexOf("xhi")), Math.max(1, str.indexOf("hi")));
return countHi2(str.substring(nextIndex));

Right now you do recursion to look at each character, which takes a lot of time. It's my personal opinion you should be using iteration for a problem like this, but alas, the rules of the challenge say you must use recursion.

For me, however, that doesn't seem to stop me from checking for the next instance of an interesting character sequence via String.indexOf.

Another thing you could do is replace str.substring(0, 3).equals("xhi") with str.startsWith("xhi"). This makes it more clear what you're doing. You can also apply this to the "hi" string.

Lastly,

if (str.substring(0, 3).equals("xhi")) {
    return countHi2(str.substring(2));
}

Here you should advance by 3 characters, not 2.

All changes summed together, you'd get this:

public int countHi2(String str) {

    if (str.length() < 3) {
        return str.equals("hi") ? 1 : 0;
    }

    if (str.startsWith("xhi")) {
        return countHi2(str.substring(3));
    }

    if (str.startsWith("hi")) {
        return 1 + countHi2(str.substring(2));
    } else {
        int nextIndex = Math.min(Math.max(1, str.indexOf("xhi")), Math.max(1, str.indexOf("hi")));
        return countHi2(str.substring(nextIndex));
    }

}