题解 | 字符串的排列

import java.util.*;
import java.util.stream.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串ArrayList
     */
    public static ArrayList<String> Permutation(String str) {
        Set<String> sets = new HashSet<>();
        char[] marks = new char[str.length()];  // 标记已经添加过的
        // LinkedList 用于缓存，也可以用栈
        LinkedList<Character> list = new LinkedList<>();
        combNum(sets, marks, list, str.toCharArray());

        return new ArrayList<>(sets);
    }

    // 递归方式组合
    public static void combNum(Set<String> sets, char[] marks
							   , LinkedList<Character> list, char[] arr) {
        if (list.size() == arr.length) {
            sets.add(list.stream().map(String::valueOf).collect(Collectors.joining()));
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (marks[i] == 1) { // 排除已经添加的
                continue;
            }
            list.add(arr[i]);
            marks[i] = 1;

            combNum(sets, marks, list, arr); // 递归继续寻找

            list.removeLast(); // 移除已经参加过所有排列的数字
            marks[i] = 0;
        }
    }
}