Просто небольшая проблема рекурсии в Java

В настоящее время я просто работаю над некоторыми проблемами рекурсии, и в настоящее время я застрял на одном.

Проблема заключается в том, чтобы рекурсивно вставлять пробелы в строку в каждое возможное место, так что вывод выглядит примерно так:

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

В настоящее время я работаю над проблемой, и мне очень понравилось:

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

Мой код для проблемы до сих пор:

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

}
}

Это второе предложение, где я испытываю самые большие проблемы, потому что каждый раз, когда я запускаю его без комментариев, он переходит в бесконечный цикл. Я даже добавляю инструкции int trace (инструкции println), и это все равно не помогает.

Я читал это много раз, и мне просто не имеет смысла, почему это не работает.

Ответы

Ответ 1

Похоже, вы правильно выполнили первую "группировку", но не смогли получить следующие группировки.

Группы: "A BCD", "AB CD" и "ABC D". Вам нужно применить свой алгоритм к каждой из этих групп. Вы применили его к первому. Как вы их получите?

Прошло достаточно времени? Я написал решение python, чтобы посмотреть, как он будет выглядеть по сравнению с 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

Первое, что заставляет меня сомневаться в вашем коде, это то, что вы должны возвращать ряд строк, но ваше возвращаемое значение - это строка.

Возможно, вам нужно прибить базовый регистр и рекурсивный шаг.

Похоже, у вас есть начало в базовом случае. Вы можете вставить нулевые пробелы в пустую строку, поэтому

allPossibleSpacings("") -> [ "" ]

но вы не хотите вставлять пробел в конец, поэтому вам нужен второй базовый случай

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

и тогда ваш рекурсивный шаг может быть

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

Я не буду помогать вам писать это на Java, поскольку это домашнее задание, но надеюсь, что это поможет.

Ответ 3

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

сначала вызовите recurse ( "ABCD", 1);