交错两个字符串

Question

我有两个字符串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]);
    }

}

}

Answer 1

问题只是询问是否存在问题的递归算法,答案是肯定的.要查找它,请查找基本案例,然后查找"步骤".

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

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