题解 | #字符串的排列#

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<>();
        if (str == null || str.length() == 0) {
            return result;
        }

        StringBuilder temp = new StringBuilder();
        boolean[] vis = new boolean[str.length()];

        recursion(result, str, temp, vis);

        //对result使用set去重
        Set<String> set = new HashSet<>(result);
        return new ArrayList<>(set);
    }

    /**
     *
     * @param res 结果集
     * @param str 原始字符串
     * @param temp 临时字符串
     * @param vis  标记字符是否加入过临时字符串
     */
    void recursion(ArrayList<String> res, String str, StringBuilder temp,
                          boolean[] vis) {
        //如果临时字符串满了，加入最终结果
        if (temp.length() == str.length()) {
            res.add(temp.toString());
            return;
        }

        //遍历所有元素选取一个加入
        for (int i = 0; i < str.length(); i++) {
            //如果该元素已经加入过了，则不需要加入了
            if (vis[i]) {
                continue;
            }

            //标记为使用过了
            vis[i] = true;
            //加入临时字符串
            char ch = str.charAt(i);
            temp.append(ch);

            recursion(res, str, temp, vis);

            //回溯
            vis[i] = false;
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}