Recursive Longestword programming

Question

I have done it finally like what I want. Thank you all for helping and I want to emphasize that it was NOT homework.

public static void main(String[] args) {
    String input = "Java is a programming language";
            StringTokenizer st = new StringTokenizer(input);
    System.out.print(longestWord(input));

}

public static String longestWord(StringTokenizer st) {
    if (!st.hasMoreTokens()) {
        return "";

    } else {
        String token = st.nextToken(); 
        String longestInTheRest = longestWord(st);
        if (token.length() > longestInTheRest.length()) { 

            return token;

        } else {
            return longestInTheRest;
        }

Answer 1

Another solution, written in a more functional style - notice that I'm not allocating new strings in each call to the recursive method (only the split operation at the beginning allocates new strings). I also took Robert's suggestion of first converting the original problem into a recursion over arrays, it makes things simpler:

public static String longestWord(String s) {
    return longestWord(s.split("\\s+"), 0, 0);
}

public static String longestWord(String[] words, int currentIdx, int longestIdx) {
    if (currentIdx == words.length)
        return words[longestIdx];
    return longestWord(words, currentIdx + 1,
        words[currentIdx].length() > words[longestIdx].length() ? currentIdx : longestIdx);
}

The trick in the above solution, is that my recursion advances over the indexes of the string array, and not over the strings themselves. That's the reason why I avoid creating new strings at each call. No substring, copyOfRange, arraycopy, new String() or similar operations are needed, yielding a more elegant solution.

EDIT:

I simplified the above code a little, to make it easier to understand. With regard to the split method it's a standard string operation, take a look at the documentation.

public static String longestWord(String s) {        
    return longestWord(s.split(" "), 0, 0);
}

public static String longestWord(String[] words, int currentIdx, int longestIdx) {
    if (currentIdx == words.length)
        return words[longestIdx];
    int idx;  // temporarily stores the index of the current longest word
    if (words[currentIdx].length() > words[longestIdx].length())
        idx = currentIdx;
    else
        idx = longestIdx;
    return longestWord(words, currentIdx + 1, idx);
}

Answer 2

The following isn't quite right:

else if (token.length() > result.length()) {

When the above statement executes, result is always " ".

What the function should do is return the larger of: (1) the length of token; (2) the length of the word returned by the recursive call.

You might also think about whether the two s.substring() calls do exactly what you want, or whether there might be a problem. Printing out token and rest (or examining them in a debugger) might be useful.

Since this looks like homework, I'll stop here.

Answer 3

You're comparing the current word to the result, but the result is a local variable which is always set to " " (which, BTW, is not the empty string, but is a String containing a white space).

You should pass the current result as an argument to the method, and start with an empty string as the result.

You also have a bug because you don't trim your tokens, and thus consider the leading white space as part of the word.

Answer 4

In order to recursion to work, you need to pass a current state, the current longest word to compare with.

If looks as a homework, so I don't include the answer—please let me know if it was not.

Answer 5

    result = token;
    return longestWord(rest);

this is the wrong part. result saves token, but then you exit the method, enter it again and set result to " ". Add another parameter String currentLongest to the methods signature so that it will not get lost.

Answer 6

You need to test if there is a space left.

Something like

int index = s.indexOf(' ');
if (index < 0) return s;

Answer 7

I would take a slightly different approach to solve this:

First, I would transform the string into an array which lends itself better to a recursive method.

public static String longestWord(String string) {
    return longestWord(string.split(" "), "");
}

Then we can think about the recursive method. If we recursively pass in a smaller array, we know we will eventually pass in an empty array - that is our base case, we have enumerated all the elements, so just return the longest which was passed in as a parameter. In the recursive case, we check to see if the first element of the (now smaller) array is longer than the current longest, and recursively call passing in the longer of the two.

private static String longestWord(String[] strings, String currentLongest) {
    if (strings == null || strings.length == 0) {
        return currentLongest;
    }
    String[] newStrings = Arrays.copyOfRange(strings, 1, strings.length);
    String longest = strings[0].length() < currentLongest.length() ? currentLongest : strings[0];
    return longestWord(newStrings, longest);
}

Note: this can also be achieved by using indexes into the array, rather than copying it. However, in practice this is an optimisation too far - it makes it harder to read and is unlikely to benefit anyone.