2022-05-04 剑指offer 38题：字符串的全排列

java版：

/**
 * 字符串的排列
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 * 例如，输入字符串abc，则打印出由字符a, b, c所能排列出的所有字符串abc, acb, bac, bca, cab和cba。
 *
 * 详解abc全排列:
 *
 * abc第一次进入方法
 * 1，第一层递归
 *   begin 0 _ _
 *   i     0 _ _
 *   因为i == begin，不交换，递归进入下一层：begin + 1
 *
 * 2，第二层递归
 *   begin _ 1 _
 *   i1    _ 1 _
 *   因为i == begin，不交换，递归进入下一层：begin + 1
 *
 * 3，第三层递归
 *   begin _ _ 2
 *   因为 begin == chs.length - 1，得到一个结果，退回上层递归
 *
 * 4，第二层递归
 *   begin _ 1 _
 *   i1    _ 1 _
 *   不交换，进入下次循环
 *
 * 5，第二层递归中的循环：i1++
 *   begin _ 1 _
 *   i1    _ _ 2
 *   交换chs[1]，chs[2]，chs变成acb
 *   递归进入下一层：begin + 1
 *
 * 6，第三层递归
 *   begin _ _ 2
 *   因为 begin == chs.length - 1，得到一个结果，退回上层递归
 *
 * 7，第二层递归
 *   begin _ 1 _
 *   i1    _ _ 2
 *   执行交换还原，chs又恢复成abc
 *   因为i1 == 2，本次循环结束，退回上层递归
 *
 * 8，第一层递归
 *   begin 0 _ _
 *   i     0 _ _
 *   不交换，进入下次循环
 *
 * 9，第一层递归中的循环：i++
 *   begin 0 _ _
 *   i     _ 1 _
 *   交换chs的0和1位，chs变成bac
 *   递归进入下一层：begin + 1
 *
 * 8，第二层递归
 *   begin _ 1 _
 *   i1    _ 1 _
 *   不交换，递归进入下一层：begin + 1
 *
 * 9，第三层递归
 *   begin _ _ 2
 *   因为 begin == chs.length - 1，得到一个结果，退回上层递归
 *
 * 10，第二层递归
 *   begin _ 1 _
 *   i1    _ 1 _
 *   不交换还原，进入下一次循环
 *
 * 11，第二层递归中的循环：i++
 *   begin _ 1 _
 *   i1    _ _ 2
 *   交换chs的1和2位，chs变成bca
 *   递归进入下一层
 *
 * 12，第三层递归
 *   begin _ _ 2
 *   因为 begin == chs.length - 1，得到一个结果，退回上层递归
 *
 * 13，第二层递归
 *   begin _ 1 _
 *   i1    _ _ 2
 *   交换还原，chs变成bac
 *   因为i1为2，循环结束，退回上层递归
 *
 * 14，第一层递归
 *   begin 0 _ _
 *   i     _ 1 _
 *   交换还原，chs变成abc
 *   开始下一次循环
 *
 * 15，第一层递归中的循环：i++
 *   begin 0 _ _
 *   i     _ _ 2
 *   因为 i != begin，交换chs的0和2位，chs变成cba
 *   递归进入下一层：begin + 1
 *
 * 16，第二层递归
 *   begin _ 1 _
 *   i1    _ 1 _
 *   不交换，递归进入下一层：begin + 1
 *
 * 17，第三层递归
 *   begin _ _ 2
 *   因为 begin == chs.length - 1，得到一个结果，退回上层递归
 *
 * 18，第二层递归
 *   begin _ 1 _
 *   i1    _ 1 _
 *   不交换，进入下次循环
 *
 * 19，第二层递归中的循环：i++
 *   begin _ 1 _
 *   i1    _ _ 2
 *   交换，chs变为cab
 *   递归进入下一层
 *
 * 20，第三层递归
 *   begin _ _ 2
 *   因为 begin == chs.length - 1，得到一个结果，退回上层递归
 *
 * 21，第二层递归
 *   begin _ 1 _
 *   i1    _ _ 2
 *   交换还原，chs变为cba
 *   循环结束，返回上层递归
 *
 * 22，第一层递归
 *   begin 0 _ _
 *   i     _ _ 2
 *   交换还原，chs变为abc
 *   循环结束，退出递归
 *
 *
 *
 */
public class StringPermutation {

    public static List<String> solution1(String str) {
        List<String> list = new ArrayList<>();
        permutation(0, str.toCharArray(), list);
        Collections.sort(list);
        return list;
    }

    /**
     * 固定第一位，排列后面的位
     * @param chs
     * @param list
     * @param begin
     */
    private static void permutation(int begin, char[] chs, List<String> list) {
        if (begin == chs.length - 1) {
            list.add(new String(chs));
            return;
        }
        
        for (int i = begin; i < chs.length; i++) {
            // 如果值相等，不交换
            if (i != begin && chs[i] == chs[begin]) {
                continue;
            }
            if (i != begin) swap(chs, begin, i);
            permutation(begin + 1,chs, list);
            if (i != begin) swap(chs, begin, i);

        }
    }

}