参考大佬的博客
问题描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
问题分析
String.valueOf() 方法将不同类型打印成字符串。 Collection.sort（） 将字符串排序的流程即从第1位开始和后面每位数进行交换然后递归到第二位进行同样操作。 如果字符串中含有相同的字符则需要注意！ 去重的全排列就是从第一个数字起，每个数分别与它后面非重复出现的数字交换。这次同样要注意保持原有数据结构不变！具体由在递归后加一个swap，将替换的元素替换回来完成。
import java
.util
.ArrayList
;
import java
.util
.Collections
;
import java
.util
.HashSet
;
import java
.util
.Set
;
public class Solution {
public ArrayList
<String> Permutation(String str
) {
ArrayList
<String> arrayList
=new ArrayList<>();
char[] chars
=str
.toCharArray();
Permutation(arrayList
,0,chars
);
Collections
.sort(arrayList
);
return arrayList
;
}
private void Permutation(ArrayList
<String> arrayList
,int i
,char[] chars
){
if (i
==chars
.length
-1)
arrayList
.add(String
.valueOf(chars
));
Set
<Character> set
=new HashSet<>();
for (int j
=i
;j
<chars
.length
;j
++){
if (i
==j
||!set
.contains(chars
[j
])){
set
.add(chars
[j
]);
swap(chars
,j
,i
);
Permutation(arrayList
,i
+1,chars
);
swap(chars
,j
,i
);
}
}
}
private void swap(char[] chars
,int i
,int j
){
char temp
=chars
[i
];
chars
[i
]=chars
[j
];
chars
[j
]=temp
;
}
}
