面试题38. 字符串的排列(较难)

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

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

示例:

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

限制：

1 <= s 的长度 <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof

思路：

本问题其实就是求所有字符的排列组合，针对这种问题，也可以利用回溯进行解决，但要求不能重复，因此需要进行剪枝。

比如字符串 abc ，如果让我们求所有排列，肯定是：

先固定第 1 位，从 a 、b 、 c 中选一个，比如 a。
在以 a 为第 1 位的前提下，固定第 2 位，从 b 、 c 中选一个，比如 b。
此时第 3 位也没有可以选择的余地了，只剩下 c，这一步就走完了。
退回第 2 步，依旧在第 2 位，这次选择 c 。
此时第 3 位也没有可以选择的余地了，只剩下 b，这一步也走完了。
退回第 1 步。
从上面，你可以总结出，正常的回溯，就是先走一条路，当结束后，退回上一步继续走，反复执行，直至退无可退，结束流程。

我们可以发现，最终是没有可以选择的余地，这在程序里可以理解为，运行到下一位时，不能使用之前使用过的数据，因此会涉及到字符交换。

但因为会进行回溯，所以数字可以在回溯后再换回去，从而不影响下一次的回溯。

那什么叫剪枝呢？就是要排除一些情况，针对本题，就是要排除重复的情况。

也就是在同一位置，不能出现两次相同的字符，因为第 2 次出现时，之前肯定已经针对这种情况，所有路线都已经走过了。

因此可以联想到使用集合，存储当前位置出现过的字符，如果重复，就可以直接跳过。

作者：death00
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/jian-zhi-offer-38-zi-fu-chuan-de-pai-lie-java-hui-/

这里剪枝没搞定，需要回看重写

代码：

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
class Solution {
    Set<String> outset = new HashSet<>();//用来记录方案
    char[] c;
    public String[] permutation(String s) {
        //排列树，回溯 
        c = s.toCharArray();//字符串转成字符数组
        BackTrack(c,outset,0);//从0下标开
        return outset.toArray(new String[outset.size()]);
    }
    public void BackTrack(char[] c,Set outset,int n){//n为考察的下标
        if(n==c.length-1){
            outset.add(String.valueOf(c));//如果已经循环到最后一个字符了，就加入outset，set可以自己去重，不用单独判断
            return;
        }
        //排列树，所以有交换，这里需要剪枝，这里不完善，这个set用的有问题
        // Set<Character> set = new HashSet<>();
        for(int i=0;i<c.length;i++){
            // if(set.contains(c[i])) continue;//如果已经访问过了，直接跳过
            // set.add(c[i]);
            swap(c,i,n);
            BackTrack(c,outset,n+1);
            swap(c,i,n);
        } 
    }
    //交换
    public void swap(char[] c,int i,int j){
        char temp=c[i];
        c[i]=c[j];
        c[j]=temp;
    }
}