题目描述

编写一个方法，确定某字符串的所有排列组合。

给定一个string A和一个int n,代表字符串和其长度，请返回所有该字符串字符的排列，保证字符串长度小于等于11且字符串中字符均为大写英文字符，排列中的字符串按字典序从大到小排序。(不合并重复字符串)

测试样例：

"ABC"

返回：

["CBA","CAB","BCA","BAC","ACB","ABC"]

共有N!个
推理过程 字符 放到前面 中间 后面

解法

迭代逐步生成(集合)

package CC150;

import java.util.ArrayList;

public class _905_字符串全排列 {
    public static void main(String[] args) {
        String A = "ABC";
        System.out.println(solve(A));
    }

    private static ArrayList<String> solve(String A) {
        ArrayList<String> res = new ArrayList<>();
        int len = A.length();
        res.add(A.charAt(0) + "");//初始化,包含第一个字符

        for (int i = 1; i < len; i++) {//第二个字符插入到前面生成集合的每个元素里
            ArrayList<String> res_new = new ArrayList<>();
            String c = A.charAt(i) + "";//新字符
            //插入到每个字符，形成一个新串
            for (String str : res) {//访问上一趟集合中的每个字符串
                res_new.add(c +""+ str);//前加
                res_new.add(str +""+ c);//后加
                for (int j = 1; j < str.length(); j++) {//中间加
                    res_new.add(str.substring(0, j) + c + str.substring(j));
                }
            }
            res = res_new;//更新
        }
        return res;
    }
}

交换法 经典回溯全排列

简洁高效，自然处理重复 但是 无法维持字典序

先纵后横
但是该算法无法直接维持字典序

    static ArrayList<String> res=new ArrayList<>();//全局变量存储
    public static ArrayList<String> getPermutation(String A){
        char[] arr=A.toCharArray();
        Arrays.sort(arr);
        getPermutationCore(arr,0);
        return res;
    }

    private static void getPermutationCore(char[] arr, int k) {
        if(k==arr.length){//拍好了一中情况
            res.add(new String(arr));
        }
        //从k位置开始的每个字符都尝试放在新排列的k的这个个位置
        for (int i = k; i <arr.length ; i++) {
            swap(arr,k,i);//把后面的每个字符都换到k位
            getPermutationCore(arr,k+1);
            swap(arr,k,i);//回溯
        }
    }

    private static void swap(char[] arr, int k, int i) {
        char tmp=arr[i];
        arr[i]=arr[k];
        arr[k]=tmp;
    }

1949牌 类似

前缀法 （可以求第k个排列）

维持良好的字典序 入坑先入字典序小的
但是 较复杂 要处理重复 要额外处理。
每次都从头扫描 只要该字符可用，
例题 leetCode60

final static int k = 3;//我们要求的第几个字典序的排列
    static int count = 0;

    private static void permutation(String prefix, char[] arr) {
        if (prefix.length() == arr.length) {//前缀长度=字符集长度 一个排列完成
            count++;
        }
        if (count == k) {
            System.out.println(prefix);
            System.exit(0);
        }
        //每次都从头扫描，只要扫该字符可用，我们就附加前缀后面，前缀变长
        for (int i = 0; i < arr.length; i++) {
            char ch = arr[i];
            //这个字符可用：pre中出现的次数<在字符集中出现的次数
            if (count(prefix, ch) < count(arr, ch)) {
                permutation(prefix + ch, arr);
            }
        }
    }

    private static int count(String prefix, char ch) {
        int cnt = 0;
        for (int i = 0; i < prefix.length(); i++) {
            if (prefix.charAt(i) == ch) cnt++;
        }
        return cnt;
    }

    private static int count(char[] arr, char ch) {
        int cnt = 0;
        for (char c : arr) {
            if (c == ch) cnt++;
        }
        return cnt;
    }