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

输入描述：

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

 

1 import java.util.*; 2 public class Solution { 3     public ArrayList
      
        Permutation(String str) { 4         ArrayList
       
         re = new ArrayList
        
         (); 5         if (str == null || str.length() == 0) { 6             return re; 7         } 8         HashSet
         
           set = new HashSet
          
           (); 9         fun(set, str.toCharArray(), 0);10         re.addAll(set);11         Collections.sort(re);12         return re;13     }14     void fun(HashSet
           
             re, char[] str, int k) {15 if (k == str.length) {16 re.add(new String(str));17 return;18 }19 for (int i = k; i < str.length; i++) {20 swap(str, i, k);21 fun(re, str, k + 1);22 swap(str, i, k);23 }24 }25 void swap(char[] str, int i, int j) {26 if (i != j) {27 char t = str[i];28 str[i] = str[j];29 str[j] = t;30 }31 }32 }