Java中使用递归的字符串置换

Question

我看到了这篇文章，它非常努力地解释了打印所有字符串的递归解决方案。

public class Main {
    private static void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0)
            System.out.println(prefix);
        else {
            for (int i = 0; i < n; i++)
                permutation(prefix + str.charAt(i),
                        str.substring(0, i) + str.substring(i + 1));
        }
    }

    public static void main(String[] args) {
        permutation("", "ABCD");
    }
}

但当我们开始弹出堆栈时，我仍然无法得到部分。例如，递归一直进行到置换（“abcd”，“”），在这里，基大小写遇到，它打印abcd。但现在发生了什么？我们从函数调用堆栈弹出置换（“abc”,“d”）。我们用这个做什么等等？

谁能帮我解释一下吗？

另外，我需要一些关于时间复杂度的指示。不像完全的计算而是一些暗示。

Answer 1

更简单的示例:置换（“”,“abc”）,将空字符串表示为*:

* ABC + A BC + AB C - ABC *
      |      |
      |      ` AC B - ACB *
      |
      + B AC + BA C - BAC *
      |      |
      |      ` BC A - BCA *
      |
      ` C AB + CA B - CAB *
             |
             ` CB A - CBA *

注意，这看起来像是一棵侧卧的树。的确，它叫一棵树。开始时，我们会进入（“A”，“BC”）状态；我们继续调用（“ab”,“c”）,最后调用（“abc”,“”）。这里我们打印输出。然后我们记得我们有未完成的业务，我们返回到一个循环，但上一个级别的循环只有一个循环。所以我们也完成了，返回到（“A”，“BC”）级别；在“bc”中有两个元素，我们只做了“b”，所以现在轮到“c”了：我们调用（“ac”，“b”），后者再调用（“acb”，“”）。现在（“a”,“bc”）下的所有循环都完成了...但是等等，还有工作要做！因为（“”,“abc”）还有两个字母要处理。就这样，在我们通常所说的“深度优先搜索”中，一个分支一个分支地进行。

每一层都有一个循环。循环收缩（我们在左边的粗分支中迭代3次，然后在下一个级别中迭代2次，然后只有一次），但仍然有一个循环。因此，我们总共进行n*(n-1)*(n-2)*...*2*1迭代。O(n！）？