java 两个字符串的交织

Interleaving of two strings

提问by Nath

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

我有两个字符串str1和str2. 是否有任何算法可用于使用递归打印出两个字符串的所有交错？

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]);
    }

}

}

回答by Ray Toal

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}

• 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")

• 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"}

• 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"?

所以每次我们向第一个字符串添加一个字符时，我们都会通过将新字符添加到旧结果集中所有可能的位置来形成新的结果集。让我们看看我们是如何从第二个结果形成上面的第三个结果的。当我们添加“2”时，第二个结果中的每个元素如何变成第三个结果中的元素？

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

• "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", "")}

• "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.

对于纯函数式编程，这实际上更有趣一些，但是您用 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.

好吧，我只是写了愚蠢的东西！用脚本语言编写这些东西很有趣，所以我想看看它在 Java 中的样子会很棒。没有我想象的那么糟糕！在这里，它被打包为一个完整的 Java 应用程序。

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"));
    }
}

回答by ajnatural

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.

如果我正确解释了您的问题 - 您想要两个字符串中所有字符的所有排列，那么以下代码将有所帮助。您将需要编写自己的交换函数，并以某种方式获取两个字符串中所有字符的数组。该算法将从数组中的第 i 个元素到第 n 个元素进行置换。它是用 C++ 编写的，我会引用该算法的来源，但我不记得了。

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);
        }
    }
}

回答by Pa?lo Ebermann

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.

更改您的函数以返回字符串列表，然后考虑如何组合多个列表以生成您想要的所有输出。

回答by srinet.amit

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"));
}

 }

回答by Kshitij Jain

Below is the much better and simple to understand solution for this problem:

以下是针对此问题的更好且易于理解的解决方案：

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 String s1 = "abc";
    public static String s2 = "12";

    public static void interleave(int i, int j, String s) {

        if (i == s1.length() && j == s2.length()) {
            System.out.println("" + s);
        }

        if (i != s1.length()) {
            interleave(i + 1, j, s + s1.charAt(i));
        }

        if (j != s2.length()) {
            interleave(i, j + 1, s + s2.charAt(j));
        }

    }//Method ends here

    /**
     * Prints some example interleavings to stdout.
     */
    public static void main(String[] args) {

        interleave(0, 0, "");
    }//Method ends here
}//Class ends here

Program is using just simple recursive calls to find the solution.

程序仅使用简单的递归调用来查找解决方案。

回答by rhel.user

Here is another recursive solution:

这是另一个递归解决方案：

public class Interleaving2 {
    public static void main(String[] args) {
        String x = "ab";
        String y = "CD";
        int m = x.length();
        int n = y.length();
        char[] result = new char[m + n + 1];

        interleave(x, y, result, m, n, 0);
    }

    public static void interleave(String x, String y, char[] result, int m, int n, int i) {
        if (m == 0 && n == 0) {
            System.out.println(String.valueOf(result));
        }

        if (m != 0) {
            result[i] = x.charAt(0);
            interleave(x.substring(1), y, result, m - 1, n, i + 1);
        }

        if (n != 0) {
            result[i] = y.charAt(0);
            interleave(x, y.substring(1), result, m, n - 1, i + 1);
        }
    } 
}