题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。 题目链接：牛客网
解题思路
import java
.util
.*
;
public class Main {
public static ArrayList
<String> list
= new ArrayList();
public static void main(String
[] args
) {
String s
= "abc";
printList(permutation(s
));
}
public static ArrayList
<String> permutation(String str
) {
if (str
.length() == 0) {
return list
;
}
char[] ch
= str
.toCharArray();
Arrays
.sort(ch
);
backtracking(ch
,new boolean[ch
.length
],new StringBuilder());
return list
;
}
public static void backtracking(char[] chars
,boolean[] hasUesd
,StringBuilder sb
) {
if (sb
.length() == chars
.length
) {
list
.add(sb
.toString());
return;
}
for (int i
= 0;i
< chars
.length
;i
++) {
if (hasUesd
[i
]) {
continue;
}
if (i
!= 0 && chars
[i
] == chars
[i
- 1] && !hasUesd
[i
- 1]) {
continue;
}
hasUesd
[i
] = true;
sb
.append(chars
[i
]);
backtracking(chars
,hasUesd
,sb
);
sb
.deleteCharAt(sb
.length() - 1);
hasUesd
[i
] = false;
}
}
public static void printList(ArrayList list
) {
for (int i
= 0;i
< list
.size();i
++) {
System
.out
.print(list
.get(i
) + " ");
}
}
}
测试结果
