I am new to Java, and I'm trying to figure out how to count Characters in the given string and threat a combination of two characters "eu" as a single character, and still count all other characters as one character.

And I want to do that using recursion.

Consider the following example.

Input:

"geugeu"

Desired output:

4   // g   eu   g   eu = 4

Current output:

2

I've been trying a lot and still can't seem to figure out how to implement it correctly.

My code:

public static int recursionCount(String str) {
    if (str.length() == 1) {
        return 0;   
    }
    else {
        String ch = str.substring(0, 2);
        if (ch.equals("eu") {
            return 1   recursionCount(str.substring(1));
        }
        else {
            return recursionCount(str.substring(1));
        }
    }
}

CodePudding user response：

OP wants to count all characters in a string but adjacent characters "ae", "oe", "ue", and "eu" should be considered a single character and counted only once.

Below code does that:

public static int recursionCount(String str) {
    int n;
    n = str.length();
    if(n <= 1) {
        return n; // return 1 if one character left or 0 if empty string.
    }
    else {
        String ch = str.substring(0, 2);
        if(ch.equals("ae") || ch.equals("oe") || ch.equals("ue") || ch.equals("eu")) {
            // consider as one character and skip next character
            return 1   recursionCount(str.substring(2));
        }
        else {
            // don't skip next character
            return 1   recursionCount(str.substring(1));
        }
    }
}

CodePudding user response：

Recursion explained

In order to address a particular task using Recursion, you need a firm understanding of how recursion works.

And the first thing you need to keep in mind is that every recursive solution should (either explicitly or implicitly) contain two parts: Base case and Recursive case.

Let's have a look at them closely:

• Base case - a part that represents a simple edge-case (or a set of edge-cases), i.e. a situation in which recursion should terminate. The outcome for these edge-cases is known in advance. For this task, base case is when the given string is empty, and since there's nothing to count the return value should be 0. That is sufficient for the algorithm to work, outcomes for other inputs should be derived from the recursive case.

• Recursive case - is the part of the method where recursive calls are made and where the main logic resides. Every recursive call eventually hits the base case and stars building its return value.

In the recursive case, we need to check whether the given string starts from a particular string like "eu". And for that we don't need to generate a substring (keep in mind that object creation is costful). instead we can use method String.startsWith() which checks if the bytes of the provided prefix string match the bytes at the beginning of this string which is chipper (reminder: starting from Java 9 String is backed by an array of bytes, and each character is represented either with one or two bytes depending on the character encoding) and we also don't bother about the length of the string because if the string is shorter than the prefix startsWith() will return false.

Implementation

That said, here's how an implementation might look:

public static int recursionCount(String str) {
    if(str.isEmpty()) {
        return 0;
    }

    return str.startsWith("eu") ?
        1   recursionCount(str.substring(2)) : 1   recursionCount(str.substring(1));
}

Note: that besides from being able to implement a solution, you also need to evaluate it's Time and Space complexity.

In this case because we are creating a new string with every call time complexity is quadratic O(n^2) (reminder: creation of the new string requires allocating the memory to coping bytes of the original string). And worse case space complexity also would be O(n^2).

There's a way of solving this problem recursively in a linear time O(n) without generating a new string at every call. For that we need to introduce the second argument - current index, and each recursive call should advance this index either by 1 or by 2 (I'm not going to implement this solution and living it for OP/reader as an exercise).

In addition

In addition, here's a concise and simple non-recursive solution using String.replace():

public static int count(String str) {
    
    return str.replace("eu", "_").length();
}

If you would need handle multiple combination of character (which were listed in the first version of the question) you can make use of the regular expressions with String.replaceAll():

public static int count(String str) {
    
    return str.replaceAll("ue|au|oe|eu", "_").length();
}