Programmation récursive des mots longs

Question

Je l'ai finalement fait comme ce que je voulais.Merci à tous pour votre aide et je tiens à souligner que ce n'était PAS des devoirs.

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

Une autre solution, écrite dans un style plus fonctionnel - notez que je n'alloue pas de nouvelles chaînes à chaque appel à la méthode récursive (seule l'opération split au début alloue de nouvelles chaînes). J'ai également pris la suggestion de Robert de convertir d'abord le problème d'origine en une récursion sur des tableaux, cela simplifie les choses:

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

L'astuce dans la solution ci-dessus, c'est que ma récursivité avance sur les index du tableau de chaînes, et non sur les chaînes elles-mêmes. C'est la raison pour laquelle j'évite de créer de nouvelles chaînes à chaque appel. Aucun substring, copyOfRange, arraycopy, new String() ou opérations similaires ne sont nécessaires, ce qui donne une solution plus élégante.

< EDIT:

J'ai un peu simplifié le code ci-dessus, pour le rendre plus facile à comprendre. En ce qui concerne la méthode split, il s'agit d'une opération de chaîne standard, jetez un œil à 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

Ce qui suit n'est pas tout à fait exact:

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

Lorsque l'instruction ci-dessus s'exécute, result est toujours " ".

Ce que la fonction devrait faire est de renvoyer la plus grande des valeurs suivantes: (1) la longueur de token;(2) la longueur du mot renvoyé par l'appel récursif.

Vous pouvez également vous demander si les deux appels s.substring() font exactement ce que vous voulez, ou s'il y a peut-être un problème.L'impression de token et rest (ou de les examiner dans un débogueur) peut être utile.

Comme cela ressemble à des devoirs, je vais m'arrêter ici.

Answer 3

Vous comparez le mot actuel au résultat, mais le résultat est une variable locale qui est toujours définie sur " " (qui, BTW, n'est pas la chaîne vide, mais est une chaîne contenant un espace blanc).

Vous devez transmettre le résultat actuel en tant qu'argument à la méthode et commencer par une chaîne vide comme résultat.

Vous avez également un bogue parce que vous ne coupez pas vos jetons, et considérez donc l'espace blanc principal comme faisant partie du mot.

Answer 4

Pour que la récursion fonctionne, vous devez passer un état actuel, le mot le plus long actuel avec lequel comparer.

Si cela semble être un devoir, donc je n'inclus pas la réponse, merci de me le faire savoir si ce n'est pas le cas.

Answer 5

    result = token;
    return longestWord(rest);

ce n'est pas la bonne partie.result enregistre le jeton, mais ensuite vous quittez la méthode, saisissez-le à nouveau et définissez le résultat sur "".Ajoutez un autre paramètre String currentLongest à la signature des méthodes afin qu'il ne soit pas perdu.

Answer 6

Vous devez tester s'il reste un espace.

Quelque chose comme

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

Answer 7

J'adopterais une approche légèrement différente pour résoudre ce problème:

Premièrement, je transformerais la chaîne en un tableau qui se prête mieux à une méthode récursive.

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

Ensuite, nous pouvons penser à la méthode récursive.Si nous passons récursivement dans un tableau plus petit, nous savons que nous finirons par passer dans un tableau vide - c'est notre cas de base, nous avons énuméré tous les éléments, donc renvoyez simplement le plus long qui a été passé en paramètre.Dans le cas récursif, nous vérifions si le premier élément du tableau (maintenant plus petit) est plus long que le plus long courant, et appelons récursivement passant dans le plus long des deux.

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

Remarque: ceci peut également être réalisé en utilisant des index dans le tableau, plutôt qu'en le copiant.Cependant, en pratique, il s'agit d'une optimisation trop poussée - elle rend la lecture plus difficile et ne profitera probablement à personne.