要求:输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路:使用全排列算法
方法见19_全排列递归算法
public class L39_permutation {
// 全排列算法
static ArrayList<String> res = new ArrayList<>();
static char[] c;
public static String[] permutation(String str) {
// 将字符串转化为数组
c = str.toCharArray();
int len = c.length;
dfs(0,len);
// 将ArrayList转化为字符数组,先把链表的每个值取出来,然后拼接到一起,隔着",",利用字符分割split(",")切分成数组
StringBuilder sb = new StringBuilder();
for(int i=0; i<=res.size()-1;i++){
sb.append(res.get(i)+",");
}
String[] val = sb.deleteCharAt(sb.length()-1).toString().split(",");
return val;
}
//递归
public static void dfs(int m, int len){
HashSet<Character> set = new HashSet<>();
if(m == len){
res.add(String.copyValueOf(c));
}else{
for(int i=m; i<len;i++){
// 如果有重复的字符,要剪掉,即相同的字母只固定一次
if(set.contains(c[i])) continue; // 重复,因此剪枝
set.add(c[i]);
// 交换,固定第一位
char temp = c[m];
c[m] = c[i];
c[i] = temp;
// 递归
dfs(m+1, len);
// 交换回去
temp = c[m];
c[m] = c[i];
c[i] = temp;
}
}
}
public static void main(String[] args) {
String[] str = permutation("abbb");
int len = str.length;
for(int i=0; i<len;i++){
System.out.println(str[i]);
}
}
}
网友评论