描述

输入一个字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述：

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

示例1

输入："ab"

返回值：["ab","ba"]

说明：

返回["ba","ab"]也是正确的

示例2

输入："aab"

返回值：["aab","aba","baa"]

示例3

输入："abc"

返回值：["abc","acb","bac","bca","cab","cba"]

第一种解决方法，对于一个长度为n的字符串来说，它所有字符的排列组合数量为 n!（n*（n-1）...1*）,对于第一个字符来说，它的选择是有n中，而第二个字符就只有n-1种了，依次类推，最后一个字符只有一种选择，可以选择递归来实现，代码如下。

public ArrayList<String> firstPermutation(String str) {
        ArrayList<String> arrayList = new ArrayList<>();
        if (null == str || str.length() < 1) {
            return arrayList;
        }
        messageStr(arrayList, 0, str.toCharArray());
        return arrayList;
    }

    public void messageStr(ArrayList<String> arrayList, int start, char[] chars) {
        //说明是最后一个字符了
        if (start == chars.length - 1) {
            String s = String.valueOf(chars);
            if (!arrayList.contains(s)) {
                arrayList.add(s);
            }
        } else {
            for (int i = start; i < chars.length; i++) {
                swap(chars, i, start);
                messageStr(arrayList, start+1, chars);
                //交换回位置，为了确保字符顺序不被改变
                swap(chars, i, start);
            }
        }

    }

    private void swap(char[] chars, int i, int j) {
        char tmp = chars[i];
        chars[i] = chars[j];
        chars[j] = tmp;
    }

第二种解法，直接将所有情况列举出来，比如a,就只有一种情况，ab则有两种情况，ab,ba，如果此时再加一个c进来，变成abc,这个c可以放ab的前面，可以放ab的中间，也可以放ab的后面，依次类推，我们遍历所有情况即可，最后对list去个重即可，代码如下

public ArrayList<String> secondPermutation(String str) {
        ArrayList<String> arrayList = new ArrayList<>();
        if (null == str || str.length() < 1) {
            return arrayList;
        }
        //将第一个数字放入集合李
        arrayList.add(str.charAt(0)+"");
        for(int i = 1; i < str.length(); i++){
            ArrayList<String> resList = new ArrayList<>();
            char c = str.charAt(i);
            for (String s : arrayList) {
                //放s前面
                String result =  c + s;
                resList.add(result);
                //放s后面
                result = s + c;
                resList.add(result);
                // 加在中间
               for (int j = 1; j < s.length(); j++) {
                   result = s.substring(0, j) + c + s.substring(j);
                   resList.add(result);
                }
            }
            arrayList = resList;
        }
        return (ArrayList<String>) arrayList.stream().distinct().collect(Collectors.toList());
    }