字符串的排列【Java版】

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
感谢牛客@LiuNing的图，来借用一下：

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    ArrayList<String> res = new ArrayList<String>();
    public ArrayList<String> Permutation(String str) {
        if(str == null || str.equals(""))return res;
        exchange(str.toCharArray(), 0);//【str==>char[]】  //String格式转化为char数组，方便交换操作
        Collections.sort(res);//最终输出前，要一次排序（字典序），不然每个人的答案不一样OG难以判断
        return res;
    }
    public void exchange(char [] ch, int left){//传ch[]是因为这个被递归改成无数个版本副本，而res只有唯一版本 所以提到外面
        if(left == ch.length-1){//left到了char[]数组的最后一个，才开始判重入列。否则长度不够的情况下都要继续向下分支
            if(!res.contains(new String(ch))){//由于输入的str可能有重复字母，所以要去重；否则按照这个算法，如果原str无重复是不需要去重的（每个都能用得上）
                res.add(new String(ch));//要new String对象 //看下还有没有别的方式？？
            }
        }
        else{
            for(int right=left; right<=ch.length-1; ++right){//从j=i开始，意思是第一个交换是，保留原来的ch,而并不会真正交换
                swap(ch, left, right);
                exchange(ch, left+1);//深入
                swap(ch, right, left);//还原,for循环下一轮还要用 原始版的
            }
        }
    }
    public void swap(char [] ch, int i, int j){//swap不用返回，直接改ch[]
        char temp = ch[i];
        ch[i] = ch[j];
        ch[j] = temp;
    }
}
//【时间复杂度分析】
//下面的 N都是代表str的length, 比如 abc是3
//递归调用exchange()函数次数: N*(N-1)*(N-2)*...*1 = N！次
//判重：一共 N!次；每次的时间复杂度为O(N!) ==>因为要和res里面的所有str去比较
//综上，本题时间复杂度为 O(N!*N!)
//【空间复杂度分析】
//如果包括系统栈空间的话，每个递归exchange()函数都需要一个ch[]，其大小为N
//那么总空间为：O(N!)*O(N) = O((N+1)!)