剑指 Offer.38-字符串的排列

class Solution {
    //创建全局变量存储结果
    List<String> res = new LinkedList<>(); 
    
    char[] c; //维护一个当前字符串的字符数组
    
    public String[] permutation(String s) {
        c = s.toCharArray();
        recur(0);
        return res.toArray(new String[res.size()]);
    }

    //定义回溯算法 通常回溯通过dfs实现
    void recur(int index){
        // 递归出口 到达字符串末尾时
        if(index == c.length-1) {
            res.add(String.valueOf(c));
            return;
        }
        // 可能出现重复的情况，引入hashset进行去重
        HashSet<Character> set = new HashSet<>();
        // 模拟排列树的建立
        for(int i = index;i < c.length;i++){
            // 通过这个循环遍历所有可能 0 a,b,c 1 b,c 2 c 同时通过set的特性将重复元素去除
            if(set.contains(c[i])) continue;
            set.add(c[i]);
            swap(i,index);
            recur(index+1);
            swap(i,index);
        }
    }
    
    void swap(int a,int b){
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;  
    }
}