什么是不重复的字符串全排列？对于序列acc，它的全排列为acc、acc、cac、cca、cca、cac，其中acc和cca各出现两次。为了解决这个问题，我们需要找到一种方法，能够在生成全排列的过程中，避免产生重复的排列。
如果是普通字符串全排列，那么
输入：
acc
输出：
acc
acc
cac
cca
cca
cac
要求写出的去重的，也就是会输出：
acc
cac
cca
上代码进行比较吧，后面给出练习例题。
首先，我们有一个方法用于生成序列的全排列。然后，我们有一个方法用于交换序列中的两个元素。我们将使用这两个方法来生成序列的全排列，并通过适当的方式避免产生重复的结果。
importjava.io.BufferedInputStream; importjava.util.HashSet; importjava.util.Scanner; importjava.util.Set; publicclasstest { publicstaticvoidarrange1(char[] str, inti) { if (i==str.length) { System.out.println(str); } else { for (intj=i; j<str.length; ++j) { swap(str, i, j); arrange1(str, i+1); swap(str, i, j); } } } publicstaticvoidarrange2(char[] str, inti) { if (i==str.length) { System.out.println(str); } else { Set<Character>set=newHashSet<Character>(); // 每一层对应一个setfor (intj=i ; j<str.length; ++j) { if (!set.contains(str[j])) { // 最上面一层的串是起始串，根据起始串思考set.add(str[j]); swap(str, i, j); arrange2(str, i+1); swap(str, i, j); } } } } publicstaticvoidswap(char[] str, inti, intj) { charc=str[i]; str[i] =str[j]; str[j] =c; } publicstaticvoidmain(String[] args) { Scannercin=newScanner(newBufferedInputStream(System.in)); Stringstr=cin.next(); arrange1(str.toCharArray(), 0); System.out.println("======================"); arrange2(str.toCharArray(), 0); cin.close(); } }
对于方法arrange1，它是一个普通的全排列生成方法，不会避免产生重复的结果。而方法arrange2则使用了一种新的方式，来避免产生重复的结果。在arrange2中，我们使用了一个HashSet来存储已经尝试过的字符。这样，如果我们碰到一个已经尝试过的字符，我们就可以直接跳过，而不需要再次生成以这个字符开始的全排列。这样，我们就可以避免产生重复的全排列。
相关题目：
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
题目链接：字符串的排列_牛客题霸_牛客网
测试用例会有空串""，此时不添加进集合，还会有"aa"
分析思路（盗图一张）：
AC代码：
importjava.util.ArrayList; importjava.util.Set; importjava.util.HashSet; importjava.util.Collections; importjava.util.Comparator; publicclassSolution { ArrayList<String>list=newArrayList<String>(); publicArrayList<String>Permutation(Stringstr) { if (str.length() !=0) { Arrange(str.toCharArray(), 0); // 升序可以不用第二个参数，这里cab测试用例在cba前面，说明得排序，我个人觉得是题目有问题，排序偏离了出题人的意图Collections.sort(list, newComparator<String>(){ publicintcompare(Strings1, Strings2) { returns1.compareTo(s2); } }); } returnlist; } privatevoidArrange(char[] arr, inti) { if (i==arr.length) { list.add(newString(arr)); } else { Set<Character>set=newHashSet<Character>(); for (intj=i; j<arr.length; ++j) { if (!set.contains(arr[j])) { set.add(arr[j]); if (i!=j) { swap(arr, i, j); } Arrange(arr, i+1); if (i!=j) { swap(arr, i, j); } } } } } privatevoidswap(char[] arr, inti, intj) { chartemp=arr[i]; arr[i] =arr[j]; arr[j] =temp; } }
======================Talk is cheap, show me the code=========================
