题目描述

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

输入描述

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

思路

递归法，问题转换为先固定第一个字符，求剩余字符的排列；求剩余字符排列时跟原问题一样。
(1) 遍历出所有可能出现在第一个位置的字符（即：依次将第一个字符同后面所有字符交换）；
(2) 固定第一个字符，求后面字符的排列（即：在第1步的遍历过程中，插入递归进行实现）。

7578108_1499250116235_8F032F665EBB2978C26C4051D5B89E90.png

个人解法

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list=new ArrayList<>();
        if(str.length()==0){
           return list;
       }
       if(str.length()==1){
           list.add(str);
           return list;
       }
        
        getList(list,0,str.toCharArray());
        Collections.sort(list);//排列
        return list;
    }
    
    public void getList(ArrayList<String>list,int i,char c[]){
        
        if(i<c.length){ 
            //list中如果没有相同的，就添加
            if(!list.contains(String.valueOf(c))){
                list.add(String.valueOf(c));
            }
        }
        for(int n=i;n<c.length;n++){ //先确定第i位，对后面的i+1位进行相同的操作
            swap(c,i,n);
            getList(list,i+1,c);
            //第二个swap保证程序发生交换后，恢复到交换之前的状态。
            //举个例子：对于上图的左子树，当程序将ACB加入到list中，此时数组的状态就是ACB，
            //因为递归的原因，程序会退栈回到根节点。
            //如果没有第二个swap的话，此时的根节点是ACB，而不是ABC，显然这不是我们想要的结果。
            swap(c,i,n);
        }
    }
    
    
    public void swap(char c[],int i,int n){
        char a=c[i];
        c[i]=c[n];
        c[n]=a;
    }
}