Just a little recursion issue in Java

I'm currently just working my way through some recursion problems, and I am currently stuck on one.

The problem is to recursively insert spaces into a string, into every single possible location, such that the output looks something like:

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

I have currently worked on the problem, and got to a point much like:

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

My code for the problem so far:

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

It looks like you've been able to do the first 'grouping' correctly, but unable to get the next groupings.

The groupings are: 'A BCD', 'AB CD', and 'ABC D'. You need to apply your algorithm to each of these groupings. You've applied it to the first. How do you get the rest of them?

Has enough time passed? I wrote up a python solution just to see what it'd look like compared to 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')

answered 2011-04-02T03:30:16.723

Just a little recursion issue in Java

1 Answer

Your Answer