String Recursion Method in Java

Question

I'm trying to write a recursive program: to compute all strings of length n that can be formed from all the characters given in string, but none of the strings listed in sub are allowed to appear as substrings.

This is the program I have written so far, but it doesn't yet implement the restriction of sub, it only computes the permutations of string.

    public static void method(String string)
    {
        method(string, "");
    }
    public static void method(String string, String soFar)
    {
        if (string.isEmpty())
        {
            System.err.println(soFar + string);
        }
        else
        {
            for (int i = 0; i < string.length(); i++)
            {
                method(string.substring(0, i) + string.substring(i + 1, string.length()), soFar + string.charAt(i));
            }
        }
    }

Radu Mirea · Accepted Answer · 2020-03-15 17:04:39Z

2

From your example I see that you want all permutations with repetition for n characters, but your code generates all permutations without repetition for all characters.

This should solve your problem as stated in the example:

    public static List<String> method(String string, int n, List<String> sub)
    {
        List<String> results = new ArrayList<>();
        method(string, n, "", sub, results);
        return results;
    }
    private static void method(String string, int n,  String soFar, List<String> sub, List<String> results)
    {
        for (String s: sub)
        {
            if(soFar.length() >= s.length() && soFar.substring(soFar.length() - s.length()).equals(s))
            {
                return;
            }
        }
        if (soFar.length() == n)
        {
            results.add(soFar);
        }
        else
        {
            for (int i = 0; i < string.length(); i++)
            {
                method(string, n, soFar + string.charAt(i), sub, results);
            }
        }
    }

Also, it's redundant to append string when string is empty.

edited Mar 15, 2020 at 17:04

answered Mar 15, 2020 at 15:55

Radu Mirea

4205 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Roozilla Over a year ago

i'm trying to run the program, but the first method could only have the three variables String string int n and List<String> sub. I took out result as a variable, but I'm not quite sure how to pass an empty list (for result) when calling method in the second line. (may be a stupid question, sorry, still learning!)

Radu Mirea Over a year ago

You could declare it as private static List<String> results = new ArrayList<>(); outside the method, but I do not recommend it in this case unless you want to store all results for multiple method calls.

Roozilla Over a year ago

i'm also getting an error in the tester that says void cannot be converted to java.util.List<java.lang.String>

Roozilla Over a year ago

I'm still getting the same error, I added the tester in so you can see

Roozilla Over a year ago

oh, I just recopied and pasted it, and it's working. it passed the tester, thank you so much :)

Collectives™ on Stack Overflow

String Recursion Method in Java

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related