算法—输出字符串的全排列

题目

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

分析

参照牛客上的答案：字符串的排列

1.固定住第一个字符；
2.将第一个字符依次与后面的交换，如abc得到abc,bac,cba
3.重复步骤1，2

如abc固定住剩余串bc中的b，然后依次与后面的交换，得到abc,acb
bac固定住剩余串ac中的a，然后依次与后面的交换，得到bac,bca
cab固定住剩余串ab中的a，然后依次与后面的交换，得到cab,cba

4.判断固定的第i个字符是不是最后一个字符了，如果是，则将字符串加入list，然后返回

注意：
1.这里不能包括重复字符串，因此加入list之前要先判断是否重复
2.递归（或者回溯）到最后之后，要有一个回退到上一步的状态的操作。

代码

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<>();  //装所有的排列
        if(str == null || str.length()==0){
            return list;
        }
        PermutationHelper(str.toCharArray(), list, 0); //步骤1
        Collections.sort(list);
        return list;
    }
        public void PermutationHelper(char[] charArray, ArrayList<String> list, int i){
        //参数为字符数组charArray，装所有排列的list，需要固定的第i个字符
            if(i == charArray.length-1){ //跳出递归的条件
                if(!list.contains(new String(charArray))){ //判断是否有重复排列
                    list.add(new String(charArray));
                }
            }
            for(int j=i; j<charArray.length; j++){
                //将第i个字符依次与后面的交换
                swap(charArray, i, j);
                PermutationHelper(charArray, list, i+1);
                swap(charArray, i, j);  //递归到底之后要回退到原来的状态
            }
    }
    public void swap(char[] ch, int i, int j){
        char temp = ch[i];
        ch[i] = ch[j];
        ch[j] = temp;
    }
}