字符串的排列

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

分析：字符串拆成字符数组以便重组，使用交换字符顺序的方法，先确定第一个位置有多少种字符在上面，然后剩下后面的字符等待排序，再确定下一个位置，就可以使用递归。

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)
            return res;
        PermutationAux(str.toCharArray(), 0);
        Collections.sort(res);
        return res;
    }
    /**递归函数，将字符串的排列加入数组
    * @param: 字符数组，确认下标位置
    * @return: 无
    */
    public void PermutationAux(char[] str, int i){
        if(i == str.length - 1){
            res.add(String.valueOf(str));
        }else{
            for(int j = i; j < str.length; j++){
                if(j != i && str[i] == str[j])
                    continue;
                swap(str, i, j);
                PermutationAux(str, i+1);
                swap(str, i, j);  // 注意还原位置
            }
        }
    }
    /** 交换字符数组两个位置
    * @param: 字符数组，位置i,位置j
    * @return: 无
    */
    public void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
}