Programación recursiva de palabras largas

Question

Lo he hecho finalmente como lo que quiero. Gracias a todos por ayudar y quiero enfatizar que no era la tarea.

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

Otra solución, escrita en un estilo más funcional: observe que no estoy asignando nuevas cadenas en cada llamada al método recursivo (solo el split La operación al principio asigna nuevas cadenas). También tomé la sugerencia de Robert de convertir primero el problema original en una recursión sobre las matrices, simplifica las cosas:

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

El truco en la solución anterior es que mi recursión avanza sobre el índices de la matriz de cuerdas, y no sobre las cuerdas mismas. Esa es la razón por la que evito crear nuevas cuerdas en cada llamada. No substring, copyOfRange, arraycopy, new String() o se necesitan operaciones similares, produciendo una solución más elegante.

EDITAR:

Simplifiqué un poco el código anterior, para que sea más fácil de entender. Con respecto a la split método es una operación de cadena estándar, eche un vistazo a documentación.

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

Lo siguiente no es del todo correcto:

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

Cuando se ejecuta la declaración anterior, result es siempre " ".

Que función debería hacer es devolver el más grande de: (1) la longitud de token; (2) La longitud de la palabra devuelta por la llamada recursiva.

También podría pensar si los dos s.substring() Las llamadas hacen exactamente lo que desea, o si podría haber un problema. Imprimiendolo token y rest (o examinarlos en un depurador) podría ser útil.

Como esto parece tarea, me detendré aquí.

Answer 3

Está comparando la palabra actual con el resultado, pero el resultado es una variable local que siempre se establece en " " (que, por cierto, no es la cadena vacía, pero es una cadena que contiene un espacio en blanco).

Debe pasar el resultado actual como argumento al método y comenzar con una cadena vacía como resultado.

También tiene un error porque no recorta sus tokens y, por lo tanto, considera el espacio en blanco líder como parte de la palabra.

Answer 4

Para la recursión al trabajo, debe aprobar un estado actual, la palabra más larga actual para comparar.

Si parece una tarea, por lo que no incluyo la respuesta, por favor avíseme si no lo era.

Answer 5

    result = token;
    return longestWord(rest);

Esta es la parte incorrecta. El resultado guarda el token, pero luego sale del método, vuelve a ingresarlo y establece el resultado en "". Agregue otra cadena de parámetro CurrentLongest a la firma de métodos para que no se pierda.

Answer 6

Debe probar si queda un espacio.

Algo como

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

Answer 7

Tomaría un enfoque ligeramente diferente para resolver esto:

Primero, transformaría la cadena en una matriz que se presta mejor a un método recursivo.

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

Entonces podemos pensar en el método recursivo. Si pasamos recursivamente en una matriz más pequeña, sabemos que eventualmente pasaremos en una matriz vacía; ese es nuestro caso base, hemos enumerado todos los elementos, por lo que solo devolveremos el más largo que se pasó como parámetro. En el caso recursivo, verificamos para ver si el primer elemento de la matriz (ahora más pequeña) es más larga que la actual más larga, y la llamada recursiva pasando en el más largo de los dos.

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

Nota: Esto también se puede lograr utilizando índices en la matriz, en lugar de copiarlo. Sin embargo, en la práctica, esta es una optimización demasiado lejos: hace que sea más difícil de leer y es poco probable que beneficie a cualquiera.