Interleaving of two strings

Question

I have two strings str1 and str2. Is there any algorithm that can be used in order to print out all interleavings of the two strings using recursion?

Update:

public class Interleave {


    private String resultString[] = new String[10];
    private String[] interStr(String str1, String str2){
    int n = ((Factorial.factorial(str1.length() + str2.length())) / (Factorial.factorial(str1.length()) * Factorial.factorial(str2.length())));
    //n is number of interleavings based on (str1.length()+str2.length())! / (str1.length()! * str2.length()!)
    if(str1.length() == 0){
        resultString[0] = str2;
        return resultString;
    }

    if(str2.length() == 0){
        resultString[0] = str1;
        return resultString;
    }

    else{
        for(int i = 0; i < n; i++){
            resultString[i]= str1.substring(0, 1) + interStr(str1.substring(1), str2.substring(1));

        }
    }
    return resultString;
}

    public static void main(String[] args) {
    Interleave obj = new Interleave();
    obj.interStr("12", "abc");
    for(int i = 0; i < obj.resultString.length; i ++){
        System.out.println(obj.resultString[i]);
    }

}

}

Solution 1

The question simply asked whether a recursive algorithm exists for the problem, and the answer is yes. To find it, look for the base case and then for the "step".

The base case is when one of the two strings are empty:

• interleave(s1, "") = {s1}

• interleave("", s2) = {s2}

Notice the order of the arguments doesn't really matter, because

• interleave("ab", "12") = {"ab12", "a1b2", "1ab2", "a12b", "1a2b", "12ab"} = interleave("12", "ab")

So since the order doesn't matter we'll look at recursing on the length of the first string.

Okay so let's see how one case leads to the next. I'll just use a concrete example, and you can generalize this to real code.

• interleave("", "abc") = {"abc"}
• interleave("1", "abc") = {"1abc", "a1bc", "ab1c", "abc1"}
• interleave("12", "abc") = {"12abc", "1a2bc", "1ab2c", "1abc2", "a12bc", "a1b2c", "a1bc2", "ab12c", "ab1c2" "abc12"}

So everytime we added a character to the first string, we formed the new result set by adding the new character to all possible positions in the old result set. Let's look at exactly how we formed the third result above from the second. How did each element in the second result turn into elements in the third result when we added the "2"?

• "1abc" => "12abc", "1a2bc", "1ab2c", "1abc2"
• "a1bc" => "a12bc", "a1b2c", "a1bc2"
• "ab1c" => "ab12c", "ab1c2"
• "abc1" => "abc12"

Now look at things this way:

• "1abc" => {1 w | w = interleave("2", "abc")}
• "a1bc" => {a1 w | w = interleave("2", "bc")}
• "ab1c" => {ab1 w | w = interleave("2", "c")}
• "abc1" => {abc1 w | w = interleave("2", "")}

Although one or two examples doesn't prove a rule in general, in this case you should be able to infer what the rule is. You will have a loop, with recursive calls inside it.

This is actually a little more fun to do with pure functional programming, but you tagged the question with Java.

Hopefully this is a start for you. If you get stuck further you can do a web search for "interleaving strings" or "interleaving lists". There are some solutions out there.

EDIT:

Okay I just wrote the silly thing! It's a lot of fun to write these things in scripting languages, so I thought it would be great to see what it looked like in Java. Not as bad as I thought it would be! Here it is, packaged as an entire Java application.

import java.util.ArrayList;
import java.util.List;

public class Interleaver {

    /**
     * Returns a list containing all possible interleavings of two strings.
     * The order of the characters within the strings is preserved.
     */
    public static List<String> interleave(String s, String t) {
        List<String> result = new ArrayList<String>();
        if (t.isEmpty()) {
            result.add(s);
        } else if (s.isEmpty()) {
            result.add(t);
        } else {
            for (int i = 0; i <= s.length(); i++) {
                char c = t.charAt(0);
                String left = s.substring(0, i);
                String right = s.substring(i);
                for (String u : interleave(right, t.substring(1))) {
                    result.add(left + c + u);
                }
            }
        }
        return result;
    }

    /**
     * Prints some example interleavings to stdout.
     */
    public static void main(String[] args) {
        System.out.println(interleave("", ""));
        System.out.println(interleave("a", ""));
        System.out.println(interleave("", "1"));
        System.out.println(interleave("a", "1"));
        System.out.println(interleave("ab", "1"));
        System.out.println(interleave("ab", "12"));
        System.out.println(interleave("abc", "12"));
        System.out.println(interleave("ab", "1234"));
    }
}

Solution 2

Here is a solution using recursive approach, easy to understand too

public class Interleave {

public static List<String> interleave(String first, String second){
    if(first.length() == 0){
        List<String> list = new ArrayList<String>();
        list.add(second);
        return list;
    }
    else if(second.length() == 0){
        List<String> list = new ArrayList<String>();
        list.add(first);
        return list;
    }
    else{
        char c1 = first.charAt(0);
        List<String> listA =  multiply(c1,interleave(first.substring(1),second));
        char c2 = second.charAt(0);
        List<String> listB =  multiply(c2,interleave(first,second.substring(1)));
        listA.addAll(listB);
        return listA;
    }
}


public static List<String> multiply(char c,List<String> list){
        List<String> result = new ArrayList<String>();
        for(String str : list){
            String res = Character.toString(c) + str;
            result.add(res);
        }
    return result;
}

public static void main(String[] args){
    System.out.println(interleave("ab", "1234"));
    System.out.println(interleave("a", "b"));
    System.out.println(interleave("ab", "cd"));
}

 }

Solution 3

If I interpreted your question correctly - that you want all the permutations of all the characters in both strings, then the following code will help. You will need to write your own swap function, and somehow obtain an array of all the characters in both strings. This algorithm will permute from the i'th element up to the n'th element in the array. It is in C++, I would include a reference to where the algorithm is from but I can't remember.

void getPermutationsR(char characters[], int n, int i) 
{
    if (i == n)
    {
        //Output the current permutation
    } 
    else
    {
        for (int j=i; j<n; j++) 
        {
            swap (characters, i, j);
            getPermutationsR(characters, n, i+1);
            swap (characters, i, j);
        }
    }
}

Solution 4

What you have now is a good start. The problem is that it returns just one string, instead a list of those.

Change your function to return a list of string, and then think about how you could combine several lists to produce all the output you want.

View more solutions

Comments

[Paŭlo Ebermann]

How do you define "interleaving" of two strings?

[Paŭlo Ebermann]

Yes, but then you will have to calculate the right length before. For a list, you can simply add the elements one-by-one.

[Nath]

OK.I see. I don't know why I have to enter at least 15 characters when adding a comment.

[Paŭlo Ebermann]

They want to avoid trivial comments like "OK. I see" :-p

[Nath]

I would try to use your suggestion and Ray Toal's algorithm.

[Ray Toal]

Hint: The notation {x w | w = f(y)} means the set of all strings made by concatenating x to each of the strings returned by calling f(y). It will turn into a for loop. Hope that helps.

[Ray Toal]

@Nath It's kind of hard to pick out exactly what's wrong, but I do see you are using arrays (and fixed one at size 10, which is not a general solution) instead of lists because as you say you haven't learned them yet. This is not a great problem to use arrays for, so I suggest you bite the bullet and learn lists. To that end, I went ahead and just wrote a complete Java application for you. It should run as is.

[Nath]

Thank you very much for your help, Ray. I wouldn't be able to do it myself. One question - in the inner for loop

[Nath]

Stupid editing restrictions. I cannot edit my comment for more than 5 min.

[Nath]

So, I am reposting again the last comment: Thank you very much for your help, Ray. I wouldn't be able to do it myself. One question - in the inner for loop how the variable, that is returned by the recursive call, which here is a List is given to the variable u, which is a String?

[Nath]

Actually ignore my last question. I guess the answer is because the List contains elements that are strings. Upon every return u accepts the returned element(string).

[Ray Toal]

In Java when you say for (T x : c) it means run a for loop using the variable x of type T to go through all the elements of the collection c. The result of the recursive call is a list. The first time through the loop u is the first value of the list; the second time through u is the second and so on. The important thing is that the call is made once, THEN the for-loop runs through it, using the variable u to take on each element of the list one at a time.

[Nath]

So far in my programs I've been using the enhanced for loop when the collection has already been filled up with elements in advance. After the collection has been filled with the elements I have the statement, for example for(int value: array){...} in order to go through the array (in your code it would be through the list). This is actually the part where I got confused. Instead of filling up the list first and then having String u: list you write String u: function()

[Nath]

I apologize for keep asking questions since you've already written the code for me but there is still something that I don't understand. You are saying that the important thing is that the call is made once. As far as I understand every time when the compiler reaches for (String u : interleave(right, t.substring(1))) { we go deeper and deeper until we reach the base case, while you are saying that the call is made once. Would you mind giving me some more clarification on this? I just want to understand everything that you've written. Not to just copy it and use it.

[Ray Toal]

Well yes the call is made multiple times with in the for-i loop, and multiple times as we descend deeper into levels of recursion. I just meant that it was NOT called multiple times in the for-u loop. If you look only at the for loop that says for (String u : interleave(...) you call interleave only once and then you iterate. Contrast that with the classic-for statement like for (i=0; f(x); i++) where f(x) is called every time within that loop. Hope that answers your question!

[Ray Toal]

java.sun.com/docs/books/jls/third_edition/html/…: In for(e1;e2;e3) the expression e2 is evaluated every time through the loop. In for (type x: a) where a is an array expression, the expression a is evaluated only once.

[Nath]

OK, when I debug your code I see that for (String u : interleave(right, t.substring(1))) { calls interleave a couple of times. It winds and unwinds. Or may be there is something that I don't understand.

[Ray Toal]

Not within the for loop it doesn't! Do System.out.print("+") at the beginning of interleave and put a System.out.print(".") inside the for-u loop. You will see ranges of consecutive dots between plus signs. That will prove what I said. :)

[Nath]

I've put System.out.print("+") at the beginning of interleave and System.out.print(".") at the beginning of for (String u : interleave(right, t.substring(1))) {. In main() I have System.out.println(interleave("12", "abc"));. Through debugger I still see a couple of interleave() calls. Please, note that I am not trying to oppose what you are saying at all. I just don't get what exactly I am missing here.

[Kshitij Jain]

This solution looks very complex. See the code posted below by me. That is much simpler solution.