HashMap辅助记录字符信息

用hashmap存了字符串中字符信息，然后根据hashmap里面的信息去遍历。

import java.util.*;
import java.util.Map.Entry;

public class Solution {
   private  ArrayList<String> list = new ArrayList<String>();
    private  String ns = "";

    public  ArrayList<String> Permutation(String str) {        
        if(str == "")  return new ArrayList<String>();;
        HashMap<Character, Integer> map = new  HashMap<>();
        char[] ch = str.toCharArray();
       for(char c : ch){
           if(!map.containsKey(c))
               map.put(c, 1);
           else {
               int tmp = (int) map.get(c);
               map.remove(c);
               map.put(c, ++tmp);
           }
       }       
       return perm(map,"");//把字符串转换为map，然后求所有组成的可能。
    }

    public  ArrayList<String> perm(HashMap<Character, Integer> map,String n) {
    //如果只剩下一个字符了，则不需要再去排列了，直接在结尾打印一串就好。
        if(map.size() == 1) {            
            char c = (char)map.entrySet().iterator().next().getKey();
            int num =(int)map.entrySet().iterator().next().getValue();
            String str = new String(ns)+c;
            num--;
            if(num > 0) {//可能有一个字符出现多次。
                str += c;
            }
            list.add(str);
            return list;
        }
        Iterator<Entry<Character, Integer>> it = map.entrySet().iterator();
        while(it.hasNext()) {  //对于当前空格位，遍历目前map中所有的可能          
            Entry entry =  it.next();
            char key = (char)entry.getKey();
            int val = (int)entry.getValue();
            ns = n;
            ns += entry.getKey().toString();
           HashMap<Character, Integer> mapn = new HashMap<Character, Integer> ();//如果不new会报错。
           mapn.putAll(map);
            if(val>1) {
               mapn.put(key,--val);
            }
            else {
               mapn.remove(key);
            }
           perm(mapn,ns);
        }
        return list;
    }
}