java - 两串交织

我有两个字符串str1和str2。
是否可以使用某种算法来使用递归打印出两个字符串的所有交织？

更新:

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

}

}

最佳答案

这个问题只是问是否存在针对该问题的递归算法，答案是肯定的。要找到它，请先查找基本情况，然后再查找“步骤”。

基本情况是两个字符串之一为空时:

interleave(s1, "") = {s1}

interleave("", s2) = {s2}

注意参数的顺序并不重要，因为

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

因此，由于顺序无关紧要，我们将考虑按第一个字符串的长度递归。

好吧，让我们看看一个案例如何导致下一个案例。我将仅使用一个具体示例，您可以将其概括为实际代码。

interleave("", "abc") = {“abc”}

interleave("1", "abc") = {“1abc”，“a1bc”，“ab1c”，“abc1”}

interleave("12", "abc") = {“12abc”，“1a2bc”，“1ab2c”，“1abc2”，“a12bc”，“a1b2c”，“a1bc2”，“ab12c”，“ab1c2”，“abc12”}

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

“1abc” =>“12abc”，“1a2bc”，“1ab2c”，“1abc2”

“a1bc” =>“a12bc”，“a1b2c”，“a1bc2”

“ab1c” =>“ab12c”，“ab1c2”

“abc1” =>“abc12”

现在这样看:

“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”，“”)}

尽管一个或两个示例通常不能证明规则，但是在这种情况下，您应该能够推断出规则是什么。您将有一个循环，其中包含递归调用。

使用纯函数式编程实际上确实更有趣，但是您使用Java标记了这个问题。

希望这是您的起点。如果您陷入困境，可以在网络上搜索“交织字符串”或“交织列表”。有一些解决方案。

编辑:

好吧，我只是写了傻事!用脚本语言编写这些东西很有趣，所以我认为很高兴看到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"));
    }
}