剑指Offer-面试题38-字符串的排列

2020-05-02

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例：

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

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

思路

排列方案数量：长度为n的字符串（若不重复），排列共有n*(n-1)*(n-2)...*2*1种
方案生成方法：dfs所有排列方案。通过字符交换，先固定第1位字符（n种情况）、再固定第2位字符（n-1种情况）、… 、最后固定第n位字符（1种情况）。

不重复图解

重复方案：当存在重复字符时，排列方案也存在重复。为排除重复方案，需在固定某位字符时，保证 “每种字符只在此位固定一次” ，即遇到重复字符时不交换，直接跳过。从 DFS 角度看，此操作称为 “剪枝” 。

重复图解

递归解析：
1. 终止条件：当x=len(c)-1时，代表所有位已固定，将当前组合c转成字符串加入result并返回
2. 参数：当前固定位x
3. 递归流程：
  1. 剪枝：若c[i]在set中，代表重复，则剪枝
  2. 将c[i]加入set
  3. 固定：将c[i]和c[x]交换，即固定c[i]为当前位字符
  4. 向下层递归：dfs(x+1)
  5. 还原交换：将c[i]和c[x]交换（换回来）

代码

class Solution{
    //存储排列方案
    List<String> result = new LinkedList<>();
    //待排列字符串
    char[] c;
    public String[] permutation(String s){
        //将字符串转char数组
        c = s.toCharArray();
        //从第一个开始
        dfs(0);
        //将结果list转成字符串数组并返回
        return result.toArray(new String[result.size()]);
    }
    //dfs遍历求出排列方案
    public void dfs(int x){
        //若固定的是最后一个，则将char数组转字符串并加入到result中
        if(x == c.length-1){
            result.add(String.valueOf(c));
        }
        //使用HashSet来判断重复字符
        HashSet<Character> set = new HashSet<>();
        //从当前位x开始固定字符
        for(int i=x;i<c.length;i++){
            //如果有重复，则剪枝
            if(set.contains(c[i])){
                continue;
            }
            //将当前位字符加入set
            set.add(c[i]);
            //开启交换，将c[i]固定在x位
            swap(i,x);
            //固定后向下层递归
            dfs(x + 1);
            //递归返回后需要还原交换
            swap(i,x);
        }
    }
    //交换函数
    public void swap(int a,int b){
        char temp = c[a];
        c[a] = c[b];
        c[b] = temp;
    }
}

思路参考大佬
作者：jyd
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。