CODEWITHSUNDEEP
javastringrecursion
NOdame
NOdame

Reputation: 11

Find longest word in a sentence recursively

So I need to find the longest word recursively, I've written the code, but it's not working, and I have no idea what to fix.

        public static String longestWord(String sentence)
{
    int i = sentence.indexOf(" ");

    if (i==-1){
        return sentence;
    }

    else{
        String first = sentence.substring(0,i);
        String rest = sentence.substring(i+1);

            if(first.length()>=rest.length()){
                return longestWord(first);
            }
        else{
            return longestWord(rest);

        }

    }
}

Upvotes: 1

Views: 4024

Answers (5)

Chandu
Chandu

Reputation: 41

package com.kota.java;
import java.util.*;

class LongestWord{
    String str = "Ram is intelligent boy";
    String stringArray[] = str.split("\\s");

    public String compare(String st1, String st2) {
        if (st1.length() > st2.length()) {
            return st1;
        } else {
            return st2;
        }
    }

    LongestWord() {
        String word = "";
        for (int i = 0; i < stringArray.length; i++) {
            if (i == 0) {
                word = stringArray[0];
            }
            word = compare(word, stringArray[i]);
        }
        System.out.println("Longest word = " + word);
    }

    public static void main(String[] args) {
        new LongestWord();
    }
}
/**
 * Out put : Longest word = intelligent
 * 
 * */

Upvotes: 1

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 235994

This is another approach to solve the question:

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

private static String longest(String[] words, int idx, int longest) {
    if (idx == words.length)
        return words[longest];
    return longest(words, idx+1,
        words[idx].length() > words[longest].length() ? idx : longest);
}

First, in longestWord() the sentence gets split by its spaces, producing an array of words. From that point on, the method longest() recursively iterates over all the words passing the index of the longest one found so far in the longest parameter, until there are no more words. This is an efficient answer, as it doesn't create substrings at each step.

Upvotes: 1

Kaz
Kaz

Reputation: 58510

Your basic approach is sane: you're breaking the input into two: the first word, and the rest of the string. But then the logic is bungled a little bit.

If the first word is longer than the entire rest of the string, you should just return first, not longestWord(first) (although, you do handle that case: longestWord will notice that the word cannot be split and just return it. It's pointless though).

Secondly, if that is not the case, you cannot assume that the first word is not the longest word. You must capture the return value of longestWord(rest), and then compare that word's length to the length of first. If that word is longer, then return it. Otherwise return first.

The essence of "divide and conquer" by recursion is that you solve some smaller versions of the problem, and then integrate those results. Don't forget this second part. This is not a binary search tree search where the data is organized such that you can just recurse to one half of the space or the other to find the answer. You don't know where the longest word might be.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726489

The reason it does not work is that you are ignoring the length of the longestWord(rest): instead of comparing the length of the initial word and the rest of the sentence, you should compare the length of the initial word to the length of the longest word found in the rest of the sentence.

String first = sentence.substring(0,i);
String rest = longestWord(sentence.substring(i+1));
return first.length()>=rest.length() ? first : rest;

Upvotes: 1

user684934
user684934

Reputation:

The line:

if(first.length() >= rest.length())

should read like:

String res = longestWord(rest);
if(first.length() >= res.length())

Upvotes: 2

Related Questions