[数据结构与算法]字符串的排列38

力扣题解

• HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。
• String.valueOf(char c) : 将 char 变量 c 转换成字符串
• Java 集合类中的 Set.contains() 方法判断 Set 集合是否包含指定的对象。该方法返回值为 boolean 类型，如果 Set 集合包含指定的对象，则返回 true，否则返回 false。
• ArrayList提供了一个将List转为数组的一个非常方便的方法toArray

class Solution {
    List<String> res = new LinkedList<>();//存所有的序列
    char[] c;//排序的时候用
    public String[] permutation(String s) {
        c = s.toCharArray();//排序先把字符串转成[]
        dfs(0);//res是{abc,acb}
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) {
        if(x == c.length - 1) {
            res.add(String.valueOf(c));      // 添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++) {
            if(set.contains(c[i])) continue; // 重复，因此剪枝
            set.add(c[i]);
            swap(i, x);                      // 交换，将 c[i] 固定在第 x 位
            dfs(x + 1);                      // 开启固定第 x + 1 位字符
            swap(i, x);                      // 恢复交换
        }
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}