字符串的全排列

题目描述

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

实现：

import java.util.ArrayList;
import java.util.TreeSet;
public class Solution {
    public ArrayList<String> Permutation(String str) {
       ArrayList<String> list = new ArrayList<>();
        if (str == null || str.length() == 0)
            return list;
        char[] chs = str.toCharArray();
        TreeSet<String> tmp = new TreeSet<>();
        mutation(chs, 0, tmp);
        list.addAll(tmp);
        return list;
    }
    public void mutation(char[] chs, int start, TreeSet<String> tmp) {
        if (start == chs.length - 1) {
            tmp.add(String.valueOf(chs));
        } else {
            for (int i = start; i < chs.length; i++) {
                swap(start, i, chs);
                mutation(chs, start + 1, tmp);
                swap(start, i, chs);
            }
        }
    }

    public void swap(int i, int j, char[] chs) {
        char ch = chs[i];
        chs[i] = chs[j];
        chs[j] = ch;
    }
}