题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述：输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
示例1
输入："ab"
返回值：["ab","ba"]

题目分析

这是一个典型的排列问题，形如“给定一组数据，求这些数据所有的排列情况”，在这里一组数据就是字符串的字符。
字符串的排列情况就是，每次需要选择一个字符（不能重复选择），按照顺序将选择的字符连接起来，可以用如下的树结构来描述选择情况。
图片说明
这样产生的排列结果为abc,acb,bac,bca,cab和cba。

解题思路

针对排列问题，就是做选择的过程，我们需要进行n次选择，每次需要记录选择的数据且不能重复选择，具体过程如下：
1.遍历字符串中的字符，选择一个下标未加入过的字符（因为有重复不能比较字符值）加入记录中；
2.重复1过程，直到字符串中的字符都加入到了记录中；
3.撤销上一次的选择，选择上一次选择的下一个字符，并重复1,2；
4.直到上一次选择的下一个字符为空，选择过程结束。
在求排列的代码实现中，常使用回溯的方式，实现上述过程的回溯框架如下：

// 排列结果
List<String> res;
// 字符数组chars，选择数据记录memo
backtrack(char[] chars, StringBuilder memo){
    if(memo.length() == chars.length && res中没有memeo){
         /将memo加入到res中，并返回
    }
    for(int i=0;i<chars.length;i++){  
        if(memo中有chars[i]字符) 跳过；
        memo.append(chars[i]);// 做选择，memo加入此字符
        backtrack(chars, memo); //回溯
        memo.deleteCharAt(memo.length()-1); // 撤销选择，返回上一次选择
    }
}

代码实现

方法一：回溯+记录

ArrayList<String> result = new ArrayList<String>();
    public ArrayList<String> Permutation(String str) {
        if(str == null || str.length() == 0) return result;
        char[] charStr = str.toCharArray();
        // 按字典序排序
        Arrays.sort(charStr);
        // 存储字符顺序
        StringBuilder track = new StringBuilder();
        // 存储已经访问的字符下标
        HashMap<Integer, Character> map = new HashMap<>();
        // 回溯遍历
        backtrack(charStr, track, map);
        return result;
    }
    // 回溯法
    public void backtrack(char[] charStr, StringBuilder track, HashMap<Integer, Character> map){
        // 当字符数量等于字符数组长度时，才是一个完整的排列
        if(track.length() == charStr.length){
            // 因为有重复字符串，需要去重
            if(!result.contains(track.toString())){
                result.add(track.toString());
            }
            return;
        }
        // 每次都从0下标开始遍历
        for(int i=0;i<charStr.length;i++){
            if(map.containsKey(i)){
                // 排除已选择的序号（不能直接用值）
                continue;
            }
            // 做选择
            track.append(charStr[i]);
            map.put(i, charStr[i]);
            // 回溯
            backtrack(charStr, track, map);
            // 撤销选择
            track.deleteCharAt(track.length()-1);
            map.remove(Integer.valueOf(i));
        }
    }

时间复杂度：O(n×n!)，其中 n 为给定字符串的长度。这些字符的全部排列有 O(n!) 个，每个排列平均需要 O(n) 的时间来生成。
空间复杂度：O(n)。我们需要 O(n) 的栈空间进行回溯，注意返回值不计入空间复杂度。

方法二：回溯+交换（时间和空间消耗更少）

public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<String>();
        if(str == null || str.length() == 0) return result;
        char[] charStr = str.toCharArray();
        // 使用treeSet来保证结果是按照字典序排列的，不用事先排列
        TreeSet<String> resSet = new TreeSet<String>();
        Permutation(charStr,0,resSet);
        result.addAll(resSet);
        return result;
    }

    public void Permutation(char[] chars,int begin,TreeSet<String> treeSet){
        if(chars==null || chars.length==0 || begin<0 || begin>chars.length-1) { return ; }
        if(begin == chars.length-1){
            // 使用交换，可以节省原来使用的memo记录数据的空间
            treeSet.add(String.valueOf(chars));
        }else{
            for(int i=begin;i<chars.length;i++){
                swap(chars,begin,i);
                // 设定下标从上一次的下一个下标开始，可以减少循环次数
                Permutation(chars,begin+1,treeSet);
                swap(chars,begin,i);
            }
        }
    }

    public void swap(char[] chars,int begin,int i){
        char temp = chars[begin];
        chars[begin] = chars[i];
        chars[i] = temp;
    }

时间复杂度：O(n!)，其中 n 为给定字符串的长度。这些字符的全部排列有 O(n!) 个。
空间复杂度：O(n)。我们需要 O(n) 的栈空间进行回溯。