剑指offer第27题

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;

/**
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
 * 例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 * <p>
 * 思路
 * 1、找出所有可能的情况，并存储在set
 *
 * <p>
 * 2、将set元素存入ArrayList
 */
public class Solution27 {
    public ArrayList<String> Permutation(String str) {
        HashSet<String> strs = new HashSet<>();
        ArrayList<String> re = new ArrayList<String>();
        found(strs, str.toCharArray(), 0);
        re.addAll(strs);
        Collections.sort(re);
        return re;
    }

    public void found(HashSet<String> strs, char[] str, int k) {
        if (k == str.length - 1) {
            strs.add(String.valueOf(str));
            return;
        }
        for (int i = k; i < str.length; i++) {
            swap(str, i, k);
            found(strs, str, k + 1);
            swap(str, i, k);
        }
    }

    public void swap(char[] str, int i, int k) {
        char temp;
        temp = str[i];
        str[i] = str[k];
        str[k] = temp;
    }

}