什么是不重复的字符串全排列,如果是普通字符串全排列,那么
输入:
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<Character> set = new HashSet<Character>(); // 每一层对应一个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(可能有字符重复),字符只包括大小写字母。
测试用例会有空串"",此时不添加进集合,还会有"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<String> list = new ArrayList<String>();
public ArrayList<String> Permutation(String str) {
if (str.length() != 0) {
Arrange(str.toCharArray(), 0);
// 升序可以不用第二个参数,这里cab测试用例在cba前面,说明得排序,我个人觉得是题目有问题,排序偏离了出题人的意图
Collections.sort(list, new Comparator<String>(){
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<Character> set = new HashSet<Character>();
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;
}
}