Song Song - 1 year ago 103
Java Question

about java recursion to create combination of string

The question was asking me to return set containing all the possible combination of strings made up of "cc" and "ddd" for given length n.

so for example if the length given was 5 then set would include "ccddd" and "dddcc".
and length 6 would return set containing "cccccc","dddddd"

and length 7 would return set contating "ccdddcc","dddcccc","ccccddd"
and length 12 will return 12 different combination and so on

However, set returned is empty.
Can you please help?

"Please understand extremeply poor coding style"

public static Set<String> set = new HashSet<String>();

public static Set<String> generateset(int n) {

String s = strings(n,n,"");

return set; // change this

public static String strings(int n,int size, String s){

if(n == 3){
s = s + ("cc");
return "";}
if(n == 2){
s = s + ("ddd");
return "";}
if(s.length() == size)

return strings(n-3,size,s) + strings(n-2,size,s);

ajb ajb
Answer Source

I think you'll need to rethink your approach. This is not an easy problem, so if you're extremely new to Java (and not extremely familiar with other programming languages), you may want to try some easier problems involving sets, lists, or other collections, before you tackle something like this.

Assuming you want to try it anyway: recursive problems like this require very clear thinking about how you want to accomplish the task. I think you have a general idea, but it needs to be much clearer. Here's how I would approach the problem:

(1) You want a method that returns a list (or set) of strings of length N. Your recursive method returns a single String, and as far as I can tell, you don't have a clear definition of what the resulting string is. (Clear definitions are very important in programming, but probably even more so when solving a complex recursive problem.)

(2) The strings will either begin with "cc" or "ddd". Thus, to form your resulting list, you need to:

(2a) Find all strings of length N-2. This is where you need a recursive call to get all strings of that length. Go through all strings in that list, and add "cc" to the front of each string.

(2b) Similarly, find all strings of length N-3 with a recursive call; go through all the strings in that list, and add "ddd" to the front.

(2c) The resulting list will be all the strings from steps (2a) and (2b).

(3) You need base cases. If N is 0 or 1, the resulting list will be empty. If N==2, it will have just one string, "cc"; if N==3, it will have just one string, "ddd".

You can use a Set instead of a list if you want, since the order won't matter.

Note that it's a bad idea to use a global list or set to hold the results. When a method is calling itself recursively, and every invocation of the method touches the same list or set, you will go insane trying to get everything to work. It's much easier if you let each recursive invocation hold its own local list with the results. Edit: This needs to be clarified. Using a global (i.e. instance field that is shared by all recursive invocations) collection to hold the final results is OK. But the approach I've outlined above involves a lot of intermediate results--i.e. if you want to find all strings whose length is 8, you will also be finding strings whose length is 6, 5, 4, ...; using a global to hold all of those would be painful.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download