只是Java中的一个小递归问题

Question

我目前正在努力解决一些递归问题,目前我仍然坚持一个.

问题是递归地将空格插入到字符串中,放入每个可能的位置,这样输出看起来像:

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

}
}

第二个else子句是我遇到麻烦的地方,因为每次我运行它都没有注释它进入无限循环.我甚至提出了int trace语句(println语句),但它仍然没有帮助.

我已经多次阅读了它,它对我来说没有意义,为什么它不起作用.

Answer 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')