java - 两个字符串的交错

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}

• 交错("", s2) = {s2}

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

• interleave("ab", "12") = {"ab12", "a1b2", "1ab2", "a12b", "1a2b", "12ab"} = 交错(“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 = 交错(“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"));
    }
}