剑指Offer--字符串的排列

题目描述:
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串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;
    }
}