随笔记录

算法-字符串的全排列

2022-4-21 diaba 算法

package com.jiucaiyuan.net.question;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 【问题】打印一个字符串的全排列列（如果再加一个附加条件：要求不出现重复排列）
 * 【思路】第一个位置可以选择其中任意一个字符，第二个位置可以选择剩下的n-1个任何一个字符，第三个位置可以选择n-2个任何一个字符，依次类推
 *
 * @Author jiucaiyuan  2022/4/21 22:58
 * @mail services@jiucaiyuan.net
 */

public class PrintAllPermutations {
    /**
     * 字符串str的全排列，含有重复的
     *
     * @param str
     * @return
     */
    public static List<String> permutations(String str) {
        List<String> result = new ArrayList<>();
        if (str == null || str.length() == 0) {
            return result;
        }
        char[] chr = str.toCharArray();
        process(chr, 0, result);
        result.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        });
        return result;
    }

    /**
     * 当前来到i这个位置，chs[i...]都可以尝试在i位置上，后续都可以去尝试，
     * chs[0-i-1]是之前的选择，把所有字符形成的全排列放到result中
     *
     * @param chs 之前的选择所形成的的结果
     * @param i   当前这个位置
     */
    private static void process(char[] chs, int i, List<String> result) {
        if (i == chs.length) {
            result.add(String.valueOf(chs));
            return;
        }
        for (int j = i; j < chs.length; j++) {
            swap(chs, i, j);
            process(chs, i + 1, result);
            swap(chs, i, j);
        }
    }


    /**
     * 字符串str的全排列，不重复全排列
     *
     * @param str
     * @return
     */
    public static List<String> permutationsNoDuplicate(String str) {
        List<String> result = new ArrayList<>();
        if (str == null || str.length() == 0) {
            return result;
        }
        char[] chr = str.toCharArray();
        processNoDuplicate(chr, 0, result);
        return result;
    }

    /**
     * 当前来到i这个位置，chs[i...]都可以尝试在i位置上，后续都可以去尝试，
     * chs[0-i-1]是之前的选择，把所有字符形成的全排列放到result中
     * 不重复全排列
     *
     * @param chs 之前的选择所形成的的结果
     * @param i   当前这个位置
     */
    private static void processNoDuplicate(char[] chs, int i, List<String> result) {
        if (i == chs.length) {
            result.add(String.valueOf(chs));
            return;
        }
        boolean[] visit = new boolean[26];
        for (int j = i; j < chs.length; j++) {
            if (!visit[chs[j] - 'a']) {
                visit[chs[j] - 'a'] = true;
                swap(chs, i, j);
                processNoDuplicate(chs, i + 1, result);
                swap(chs, i, j);
            }
        }
    }

    private static void swap(char[] chs, int i, int j) {
        char temp = chs[i];
        chs[i] = chs[j];
        chs[j] = temp;
    }


    private static void printList(List<String> res) {
        for (String str : res) {
            System.out.println(str);
        }
    }

    public static void main(String[] args) {
        String str = "acc";
        printList(permutations(str));
        System.out.println("-----------------");
        printList(permutationsNoDuplicate(str));
    }
}