Recursive String Function (Java)

Question

Hi,

I am trying to design a function that essentially does as follows:

String s = "BLAH";

store the following to an array: blah lah bah blh bla bl ba bh ah al

So basically what I did there was subtract each letter from it one at a time. Then subtract a combination of two letters at a time, until there's 2 characters remaining. Store each of these generations in an array.

Hopefully this makes sense,

Jake

Answer 1

How did you get 'al'? Are these mixed up as well?

I would create a HashSet to hold all the permutations and pass it to a recursive method.

void foo(HastSet<String> set, String string) {
    if (string.length < 2) // base case
        return
    else {
        // add the string to the hashset
        set.add(string);

        // go through each character
        for (int i = 0; i < string.length; i++) {
            String newString = s.substring(0,i)+s.substring(i+1);
            foo(set, newString);
        }
    }
}

That's if you care about uniqueness. If not, you can use a Vector. Either way you can use toArray to get your array back.

Answer 2

This is an optimization of @voodoogiant's answer. Basically I want to postpone the word building task until the base case of the recursion. That way you can use a StringBuilder to bulid the word. So basically what the recursion does is turn on and off the bits of a boolean array that say if a certain letter has to be used in the next word.

Haven't written java code in a while, so forgive me if something doesn't compile.

void buildWords(String baseWord, boolean[] usedLetters, HashSet<String> words, int index){
    if (index == baseWord.length()){
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < index; i++){
            if (usedLetters[i])
                builder.append(baseWord.characterAt(i));
        }
        words.add(builder.toString());
    }
    else{
        usedLetters[index] = true;
        buildWords(baseWord, usedLetters, words, index+1);
        usedLetters[index] = false;
        buildWords(baseWord, usedLetters, words, index+1);
    }
}

Things you've got to be aware:

1. This can build the empty string (if al positions of the array are false).
2. This can build repeated words (if baseWord has consecutive repeated chars), and I don't remember if HashSet throws an exception when adding repeated keys.
3. Don't remember if StringBuilder method that appends a char to the end is called "append", but you get the idea.
4. Don't remember if StringBuilder method that outputs the string built is "toString", but you also get the idea.

Answer 3

You don't really need recursion to do this. Here's an iterative algorithm:

    String master = "abcd";
    final int L = master.length();

    List<String> list = new ArrayList<String>();
    list.add(master);
    Set<String> current = new HashSet<String>(list);
    for (int i = L-1; i >= 2; i--) {
        Set<String> next = new HashSet<String>();
        for (String s : current) {
            for (int k = 0; k < s.length(); k++) {
                next.add(s.substring(0, k) + s.substring(k + 1));
            }
        }
        list.addAll(current = next);
    }
    System.out.println(list);
    // prints "[abcd, abc, abd, bcd, acd, ac, ad, ab, bc, bd, cd]"

This is essentially a breadth-first search at heart. You start with a current set initially containing String master. Then at each iteration of i, you go through for (String s : current) and generate the next set, which you do by removing every possible character from s.

Effective Java 2nd Edition: Item 25: Prefer lists to arrays, but if you insist on storing in String[], you can just do the following at the end.

    String[] arr = list.toArray(new String[0]);

See also

• Fill a array with List data