Pregunta Solo un pequeño problema de recursión en Java


Actualmente estoy trabajando en algunos problemas de recursión, y actualmente estoy atascado en uno.

El problema es insertar espacios de manera recursiva en una cadena, en cada ubicación posible, de modo que la salida tenga el siguiente aspecto:

Input: ABCD
Out:
       ABCD
       A BCD
       A B CD
       A B C D
       A BC D
       AB CD
       AB C D
       ABC D

Actualmente he trabajado en el problema y llegué a un punto muy parecido a:

Input: ABCD
Out:
       ABCD
       A BCD
       A B CD
       A B C D

Mi código para el problema hasta el momento:

import java.util.Scanner;

public class Words 
{
    static int counter = 0;
    static String fString = "";
    static String fString2 = "";
    static String previous = "";
    static String input = "";
    static String other = "";

    public static String segment(String inputPrefix, String restOfString)
{
    if(restOfString.length() != 0)
    {   
        if(inputPrefix.equals(""))
        {
            fString += restOfString + "\n";
            segment(restOfString.substring(0,1), restOfString.substring(1));
        }
        else
        {
            previous += inputPrefix + " ";
            fString += previous + restOfString + "\n";
            fString2 = previous + restOfString;
            segment(restOfString.substring(0,1)
                            , restOfString.substring(1));
        }
    }
    /*else
    {
        counter++;
        other = fString2.replaceAll(" ", "");
        System.out.println(other);
        if((counter + 1) < other.length())
        {
            System.out.println("Other: " + other);
            input = other.substring(0, counter + 1);
            other = other.substring(counter + 1);
            System.out.println(counter);
            System.out.println("input: " + input);
            System.out.print("other: " + other);

            segment(input, other);
        }
        else
            return fString;
    }*/

    return fString;

}

public static void main (String[] args) 
{
    Scanner scan = new Scanner(System.in);
    System.out.print("Enter a string: ");
    String input = scan.next();
    System.out.println();
    System.out.println(segment("", input));

}
}

Esa segunda cláusula más es donde estoy teniendo más problemas, porque cada vez que la ejecuto sin comentar entra en un ciclo infinito. Incluso puse declaraciones de rastreo int (el println declaraciones) y todavía no está ayudando.

Lo he leído muchas veces y simplemente no tiene sentido para mí por qué no funciona.


32
2018-04-01 15:51


origen


Respuestas:


Parece que ha podido hacer la primera 'agrupación' correctamente, pero no puede obtener las siguientes agrupaciones.

Las agrupaciones son: 'A BCD', 'AB CD' y 'ABC D'. Debe aplicar su algoritmo a cada una de estas agrupaciones. Lo has aplicado al primero. ¿Cómo consigues el resto de ellos?

Ha pasado suficiente tiempo? Escribí una solución de Python solo para ver cómo se vería en comparación con Java.

def segment(input, separator=' ', start_from=0):
    print input
    # add spaces after each letter starting from start_from index, terminating at last letter-1
    for i in range(start_from, len(input)-1):
        # if the next letter is already a space, or this letter is a space, move on
        if separator in (input[i+1], input[i]): continue
        # whatever index we're on, do the next one recursively
        segment(input[:i] + input[i] + separator + input[i+1:], separator=separator, start_from=i+1)

segment('ABCD')

2
2018-04-02 03:30



Lo primero que me hace dudar de su código es que se supone que debe devolver una serie de cadenas, pero su valor de retorno es una cadena.

Tal vez, deberías marcar tu caso base y el paso recursivo.

Parece que tienes un comienzo en el caso base. Puede insertar cero espacios en la cadena vacía, por lo

allPossibleSpacings("") -> [ "" ]

pero no desea insertar un espacio al final, por lo que necesita un segundo caso base

allPossibleSpacings("x") -> [ "x" ]

y luego tu paso recursivo podría ser

allPossibleSpacings("x" + s) -> flatten(
    ∀ t : allPossibleSpacings(s), ["x" + t, "x " + t])

No te ayudaré a escribir eso en Java ya que es tarea, pero espero que eso ayude.


4
2018-04-01 16:01



void recurse(String myString, int start){
        System.out.println(myString);
        for(int i = start; i < myString.length; i++) {
            if (myString.charAt(i) != ' ' ){
                recurse(myString.Substring(0,i) + ' ' + myString.Substring(i), i+2);
            }
        }
    }

llamar primero con recurse ("ABCD", 1);


3
2018-04-01 16:04