面试题28：字符串的排列

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路：
把字符串分为两部分：第一部分是字符串的第一个字符，第二部分是第一个字符以后的所有字符。
用第二部分的字符逐个与第一个字符交换。

注意特殊输入：
字符串为null
字符串只有单个字符，如：a
字符串包含重复字母，如：aa, aba

另外，本题要求字符串的输出顺序保持字典序，本文代码使用TreeSet保持字典序

Java 代码如下：

import java.util.*;

public class Solution {
public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<>();
if("".equals(str)) {
return list;
        }
        TreeSet<String> set = new TreeSet<>();
char[] arr = str.toCharArray();
        split(set, arr, 0);
        list.addAll(set);
return list;
    }

public void split(TreeSet<String> list, char[] arr, int begin) {
if(begin == arr.length) {
            list.add(String.valueOf(arr));
        }

for(int i = begin; i < arr.length; i++) {
if(begin != i && arr[begin] == arr[i]) continue;
            swap(arr, begin, i);
            split(list, arr, begin + 1);
            swap(arr, begin, i);
        }
    }

public void swap(char[] arr, int a, int b) {
char temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}