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

Why use recursion? anyhows, your problem is the part where you dont share result. token.length() > result.length() will likely almost always resolve to true since result.length at that point is always a string with 1 space (your initial value). Specificy result as a parameter in your method and you're good to go — Polity, Jan 15 '12 at 12:48
I have done it without recursion and I am trying with recursion for preparing my exam and I understood my mistake thank you; however I couldn't repair it — John Myung, Jan 15 '12 at 13:05
Recursion add computation overhead but still it is used in many places because it's intuitive and so it's easy to program and also when the problem under study is less compute intensive. In this case recursion only makes it more complicated, so go for iteration. — John Eipe, Jan 15 '12 at 14:34

NPE · Answer 1 · 2012-01-15T12:54:12.467

3

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.

edited Jan 15 '12 at 12:54

answered Jan 15 '12 at 12:48

NPE

486,780
108
951
1,012

This is not a homework I am just trying to work for exam and your answer is very informative. I understood it but still I have something missing, thank you. – John Myung Jan 15 '12 at 13:02

score 1 · Answer 2 · answered Jan 15 '12 at 12:50

1

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.

answered Jan 15 '12 at 12:50

JB Nizet

678,734
91
1,224
1,255

Thank you I did my trim part. – John Myung Jan 15 '12 at 13:06

Óscar López · Accepted Answer · 2012-01-15T17:18:16.913

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

Same for your. It's homework, no complete solutions. -1 for you too — SHiRKiT, Jan 15 '12 at 15:10
It is good, but I don't know how to use split and I couldn't understand last return statement. Could you use another method instead of split? — John Myung, Jan 15 '12 at 15:12
OP said he's studying for an exam. And it's fine to know several different approaches for solving a problem. — Óscar López, Jan 15 '12 at 15:13
Okay, but can you explain me last return statement, I think if I will understand last return statement, it will be useful for my exam — John Myung, Jan 15 '12 at 15:18
@JohnMyung I updated my answer to make it easier to understand. As I said, `split` is standard and the simplest way to, well, split a string. — Óscar López, Jan 15 '12 at 15:21
Okay I am trying to get split method, thank you for your effort — John Myung, Jan 15 '12 at 15:29

score 0 · Answer 4 · answered Jan 15 '12 at 12:48

0

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.

answered Jan 15 '12 at 12:48

alf

8,377
24
45

it is not a homework I am just working for my final exam. Thank you for your interest – John Myung Jan 15 '12 at 13:11

score 0 · Answer 5 · answered Jan 15 '12 at 12:49

    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.

score 0 · Answer 6 · answered Jan 15 '12 at 12:52

0

You need to test if there is a space left.

Something like

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

answered Jan 15 '12 at 12:52

Peter Lawrey

525,659
79
751
1,130

Robert · Answer 7 · 2012-01-15T16:34:06.323

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.

Yeah, he indeed said it's good to post the answer, so undid the -1. Sorry. — SHiRKiT, Jan 15 '12 at 16:11

Recursive Longestword programming

7 Answers7