打印不重复的字符串全排列(递归) 数据结构与算法

什么是不重复的字符串全排列，如果是普通字符串全排列，那么
输入：
acc
输出：
acc
acc
cac
cca
cca
cac
要求写出的去重的，也就是会输出：
acc
cac
cca
上代码进行比较吧，后面给出练习例题。

import java.io.BufferedInputStream; import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class test {public static void arrange1(char[] str, int i) { if (i == str.length) { System.out.println(str); } else { for (int j = i; j < str.length; ++j) { swap(str, i, j); arrange1(str, i + 1); swap(str, i, j); } } }public static void arrange2(char[] str, int i) { if (i == str.length) { System.out.println(str); } else { Set set = new HashSet(); // 每一层对应一个set for (int j = 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); } } } }public static void swap(char[] str, int i, int j) { char c = str[i]; str[i] = str[j]; str[j] = c; }public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream(System.in)); String str = cin.next(); arrange1(str.toCharArray(), 0); System.out.println("======================"); arrange2(str.toCharArray(), 0); cin.close(); } }

相关题目：
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
题目链接：https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
测试用例会有空串""，此时不添加进集合，还会有"aa"
【打印不重复的字符串全排列(递归)】分析思路（盗图一张）：

文章图片

AC代码：

import java.util.ArrayList; import java.util.Set; import java.util.HashSet; import java.util.Collections; import java.util.Comparator; public class Solution { ArrayList list = new ArrayList(); public ArrayList Permutation(String str) { if (str.length() != 0) { Arrange(str.toCharArray(), 0); // 升序可以不用第二个参数，这里cab测试用例在cba前面，说明得排序，我个人觉得是题目有问题，排序偏离了出题人的意图 Collections.sort(list, new Comparator(){ public int compare(String s1, String s2) { return s1.compareTo(s2); } }); } return list; } private void Arrange(char[] arr, int i) { if (i == arr.length) { list.add(new String(arr)); } else { Set set = new HashSet(); for (int j = 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); } } } } } private void swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }

======================Talk is cheap, show me the code=========================