【剑指Offer】字符串的排序（全排列，结果是否去重可以考虑用list还是set）

字符串的排序（全排列）

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列（全排列）。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

扩展：全排列根据题目要求看是否去重

解题思路：递归+回溯思想

①递归：也就是穷举，把所有情况都列举出来
②回溯：在递归的过程中，回退的步骤

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<>();
        if (str != null && str.length() > 0) {
            PermutationHelper(str.toCharArray(), 0, list);
            //上图所示，左右在以C开头的字符串，结果并不是已经排好序的，所以进行sort
            //list是指值的插入顺序有序，不是指值有序
            Collections.sort(list);
        }
        return list;
    }


    //每一次递归结束的结果（cs）均存放到同一个list中（因为字符串的字符可能会有重复，所以将结果加入到list注意去重（具体看题目要求），也可以使用set集合）
    // 选择长度i为固定字符，i以后的元素全排列
    public static void PermutationHelper(char[] cs, int i, ArrayList<String> list) {
        //当前字符串排序字符已固定的长度i
        if (i == cs.length - 1) {
            //结果之一
            String s = String.valueOf(cs);
            //这里做了去重判断，原因是因为当有重复的元素时会出现相同的字符串，例：aabc
            if (!list.contains(s)) {
                list.add(s);
            }
        }else {
            for (int j = i; j < cs.length; j++) {
                // 1、交换更新长度为i的固定字符串的最后一个固定元素
                swap(cs,i,j);
                // 2、长度i以外（从下标i+1开始）的元素递归全排列
                PermutationHelper(cs,i + 1,list);
                //当以上递归函数执行结束，表示更新i处的元素后，得到一次排列
                // 进行回溯，回到字符交换以前，重新更新i处字符，重新找另一种长度固定到下标i的全排列结果
                swap(cs,i,j);
            }
        }
    }

    //swap交换操作
    public static void swap(char[] s,int i,int j) {
        char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }
}

时间复杂度更低的方法

https://www.cnblogs.com/pmars/p/3458289.html