题解 | #字符串的排列#

字符串的排列

http://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7

字符串的排列

题目

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。例如输入字符串abc,则输出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

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

分析

我这里采用递归的方式去试试，思路便参照普通列举的思路。 <!- 我希望像我这样的小白也能看懂 ->

先不考虑去重。记长度 length, 从第一个位置0开始，有length个字符选择，后面位置依次可选择的字符数依次递减，因此便考虑每选择一个位置的字符后，下一个位置的字符便从剩下的字符串里选择，这里便是递归。递归出口在，每一次把所有位置的字符选择了后，位置便到了length处，这里就将前面的字符串放进Map里，不存在则放进去。

最后将Map 里的Key拿出来，便去重了，返回即可。

以下的代码参考前人大佬的思路。

特便是那个递归与for循环的结合，真是妙啊。

代码

import java.util.*;
public class Solution {

    //小白也也能快速看懂的递归法
    
    int length=0;
    char [] arry; //以数组形式保存，方便理解    
    HashMap<String,Integer> list =new HashMap<>(); //list 保存初始的字符串  
    
    public ArrayList<String> Permutation(String str) { 
        
        arry = str.toCharArray();//工具类转换
        length=str.length();//获取长度
        
        //Arrays.sort(arry); //后面用HashMap得到key值，就不用排序，去重
        //System.out.println(arry);
        
        int k = 0;  //这个很重要，表示当前位置的字符选择。
        ArrayList<Character> arrycopy = new ArrayList<Character>(); //复制一份，因为后面用的是改变了arry,将arry用作了要保存的值。
        
        for(char a:arry){
            arrycopy.add(a);//常规复制，
        }
        //System.out.println(arrycopy);
        
        collect(arrycopy,k);  //collect 表示选择当前k位置的字符，从0开始，如果==length,表示这一次的位置上都选择了，一次完成。

        HashSet hs = new HashSet(list.keySet()); //这里用Map集合的key值拿到，即去重了，然后返回了一个set集合。
        
        ArrayList<String> res=new ArrayList<>(hs);//res 表示要保存返回的结果。
        
        return res;  
        
    }
    
    //collect 函数，
    /**
    *arrytemp 表示要在当前里的选择字符的数组
    *k 表示当前要选择字符的位置
    *
    */
    public void collect(ArrayList<Character>  arrytemp,int k){
        //如果一次的字符选择完，则选择完毕，进去查重
        if(k==length){
            String s=new String(arry);//数组转换为字符串
            if(!list.containsKey(s)){
                // 如果不存在，才添加进来。
                list.put(s,1);
            }
        }else{
            for(int i=0;i<arrytemp.size();i++){
                //这里开始，arry 表示的要生成的数组，所以，我们要将每一次arrytemp对应位置的值得到，
                //并去除已经选择了的字符，传给下一次选择
                arry[k]=arrytemp.get(i);  //选择当前位置
                ArrayList<Character> arrytemp2=new ArrayList<>(arrytemp);  //生成新的要选择的字符串
                arrytemp2.remove(i);  //去掉已经选择的字符，
                
                collect(arrytemp2,k+1); //从已经去掉选择当前字符的字符串选择下一位字符
            }
        }

    }
    
}