题目描述:
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
思路：
典型的DFS+回溯问题。
其中的坑在于如何去重。下面的代码采用的是Set集合去重。如果需要交换的两个位置的字符相等，那么就没有必要交换。
import java.util.*;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> res = new ArrayList<>();
if (str == null || str.length() == 0) {
return res;
}
char[] chs = str.toCharArray();
helper(res,chs,0);
Collections.sort(res);
return (ArrayList)res;
}
public void helper(ArrayList<String> res, char[] chs, int i){
if(i == chs.length){
res.add( new String(chs));
return;
}
HashSet<Character> set = new HashSet<>();
for(int j=i; j<chs.length;j++){
if(! set.contains(chs[j])){
set.add(chs[j]);
swap(chs,i,j);
helper(res,chs,i+1);
swap(chs,i,j);
}
}
return;
}
public void swap(char[] chs, int i, int j) {
char temp = chs[i];
chs[i] = chs[j];
chs[j] = temp;
}
}
