剑指offer38. 字符串的排列（重）

问题

剑指 Offer 38. 字符串的排列
难度：中等
输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:
输入：s = “abc”
输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]

限制：
1 <= s 的长度 <= 8

解答

排列的数量：对一个长度为 n 的字符串（字符不重复），排列的总数量为 ： n (n-1) (n-2) … *1，全排列
算法的思路：

• 利用深度遍历算法，通过字符交换，依次固定第一位（有 n 种情况），第二位（有 n - 1 种情况），…，第 n 位（只有一种情况）；
• 出现重复的字符，利用 Set 去重，当字符出现 set 中，说明匹配过了， 跳过此字符。

深度遍历的流程：
递归结束条件：当 n 到达最后一个位置，也就是 n = s.length() - 1，说明已经固定到最后一位，最后一位的情况只有一种，所以直接将排列后的字符数组生成字符串，添加到 res 中。

递归的工作： 初始化一个 Set 集合，用于去除重复固定过的字符，for 循环将 i 与 [n, s.length()] 区间位置的字符交换，固定第 n 个位置的字符，递归调用 dfs(n+1) 固定下一个位置的字符，递归返回时，再将交换的字符还原。

class Solution {
    char[] arrangement = null;
    List<String> res = null; 
    int len;
    public String[] permutation(String s) {
        res = new ArrayList<>();
        arrangement = s.toCharArray();
        len = s.length();
        arrange(0);
        return res.toArray(new String[res.size()]);
    }
    // 深度遍历，依次固定第 n 个位置的字符
    private void dfs(int n){
        if(k == len - 1){
            res.add(new String(arrangement));
            return;
        }
        Set<Character> set = new HashSet<>();
        // 逐个交换，回溯时还原。
        for(int i = n; i < len; i++){
            if(set.contains(arrangement[i]))
                continue;
            set.add(arrangement[i]);
            char t = arrangement[n];
            arrangement[n] = arrangement[i];
            arrangement[i] = t;
            dfs(n+1);
            arrangement[i] = arrangement[n];
            arrangement[n] = t;
        }
    }
}

执行结果：通过
显示详情
执行用时：9 ms, 在所有 Java 提交中击败了97.92%的用户
内存消耗：44 MB, 在所有 Java 提交中击败了100.00%的用户

数据结构用错版本，导致运行时间翻倍
原因：排列的时候已经去重了，添加结果的时候就不需要去重了，

class Solution {
    public String[] permutation(String s) {
        Set<String> res = new HashSet<>(); // 该位置换成 List
        recur(s.toCharArray(), 0, res);
        return res.toArray(new String[res.size()]);
    }
    private void recur(char[] s, int index ,Set<String> res){
        if(index >= s.length -1 ){
            res.add(String.valueOf(s));
            return;
        }  
        Set<Character> mark = new HashSet<>();
        for (int i = index; i < s.length; i ++){
            if(mark.contains(s[i]))
                continue;
            mark.add(s[i]);
            swap(s, i, index);
            recur(s, index+1, res);
            swap(s, index, i);
        }
    }
    private void swap(char[] s, int i, int j){
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }
}