题解 | #字符串的排列#

这个算法，跟之前的重复整形数的全排列算法是一样的，就是不同的一点都是变成了字符串，所以处理也变了一点

首先，可以将字符str，转变成 char[] datas = str..toCharArray();进行处理，方便操作；

其次，记录结果的数据集，output，可以用StringBuffer承接，append(datas[i])和deleteAt(i)是成对的。i的下标也是从0开始；

最后，要特别注意是的排序，要调用排序Arrays.sort(output)，有可能有“aba”这样重复的头尾重复的，导致“datas[i]==datas[i-1]”,失效，无法去重等。

import java.util.*;


public class Solution {
     ArrayList<String> res = new ArrayList<String>();
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        // 这里做异常处理
        if(str== null || str.length()==0) {
            return res;
        }
        StringBuffer output = new StringBuffer();
        boolean[] mark = new boolean[str.length()];
        char[] datas = str.toCharArray();
        // 这里特别重要，不排序 “aba”的数组会被重新计算，变成["aba","aab","baa","baa","aab","aba"]
        Arrays.sort(datas); 
        Arrays.fill(mark, false);

        backtrack(output, datas, mark);
        return res;
    }

    void backtrack(StringBuffer output, char[] datas, boolean[] mark) {
        if(output.length()== datas.length) {
            res.add(output.toString());
        }

        for(int i =0; i<datas.length; i++) {
            if(mark[i] || (i>0 && datas[i] == datas[i-1] && !mark[i-1])) {
                continue;
            }

            mark[i] = true;
            output.append(datas[i]);
            backtrack(output, datas, mark);
            mark[i] = false;
            output.deleteCharAt(output.length()-1);
        }
    }
}