剑指 Offer 38. 字符串的排列

题目

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

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

示例:

1
2
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

限制：

1 <= s 的长度 <= 8

思路

这个题有一个点：

不能有重复元素

  1. 这个不能有重复元素的意思是：数组中的一个字母只能有一次，但是可以给你重复的字母，所以我们不能用有一个hashset来判断这个元素是否已经加入（添加索引也不行，因为结果可能有重复）

    1
    2
    输入："aab"
    输出：["aba","aab","baa"]

所以我们可以通过递归的方法解决：

对于每一个元素，我们可以固定一个首部元素，然后对于后面的元素进行任意组合，然后后面的元素我们同样可以固定首部元素，对于后面的有元素进行任意组合，同时还有注意结果值可能重复的过程（我们可以在固定首部的时候排除重复的元素）。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
private static class Solution2 {
    ArrayList<String> result = new ArrayList<>();
    char[] arr;

    public String[] permutation(String s) {
        arr = s.toCharArray();
        dfs(0);
        return result.toArray(new String[result.size()]);
    }

    private void dfs(int arrIndex) {
        if (arrIndex == arr.length - 1) {
            result.add(String.valueOf(arr));
            return;
        }
        // 我们使用set判断，是否需要跳过
        HashSet<Character> set = new HashSet<>();
        for (int i = arrIndex; i < arr.length; i++) {
            if (set.contains(arr[i])) {
                continue;
            }
            set.add(arr[i]);
            // 这个交换是此方法的核心，因为这个是不能重复，所以我们可以直接在原来的数组上交换，然后这样就鞥呢遍历到每一个
            swap(i, arrIndex);
            // 这里须要用arrIndex + 1，因为我们需要回溯，这个arrIndex的值不能改变
            dfs(arrIndex + 1);
            swap(i, arrIndex);
        }

    }

    private void swap(int i, int arrIndex) {
        if (i == arrIndex) {
            return;
        }
        char temp = arr[i];
        arr[i] = arr[arrIndex];
        arr[arrIndex] = temp;
    }
}