[数据结构与算法]【剑指offer】字符的全排列

🔥题目

输入一个字符串，打印出该字符串中字符的所有排列。

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

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

?

??解析

显然，这是一个「全排列」问题。
全排列的模板（即swap交换法）不再赘述，本题的关键在于「去重」。

去重思路一：所有可能的排列结果(字符串)都存到Set集合中，让容器帮我们完成去重的操作。

去重思路二：每一次swap的本质是固定一次index处的字符，那么如果每种字符只在index处固定一次，就可以保证去重。

?

🧊代码

全排列模板+去重思路一：

class Solution {
    public String[] permutation(String s) {
        DFS(s.toCharArray(), 0);
        return res.toArray(new String[res.size()]);
    }

    private Set<String> res = new HashSet<>();

    private void DFS(char[] arr, int index) {
        if (index == arr.length) {
            res.add(new String(arr));
            return;
        }
        for (int i = index; i < arr.length; i++) {
            char temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
            DFS(arr, index + 1);
            temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }
}

全排列模板+去重思路二：

class Solution {
    public String[] permutation(String s) {
        DFS(s.toCharArray(), 0);
        return res.toArray(new String[res.size()]);
    }

    private List<String> res = new ArrayList<>();

    private void DFS(char[] arr, int index) {
        if (index == arr.length) {
            res.add(new String(arr));
            return;
        }
        Set<Character> set = new HashSet<>();
        for (int i = index; i < arr.length; i++) {
            if (set.contains(arr[i])) {
                continue;
            }
            set.add(arr[i]);
            char temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
            DFS(arr, index + 1);
            temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }
}

?

🌸补充

1）算法课上多次强调，全排列的时间复杂度是 O(n * n!)。

2）做一个区分：全排列问题使用的是swap模板，这有别于一般的回溯模板。这是因为全排列问题可以改变元素之间的相对顺序。